C-红球进黑洞
https://ac.nowcoder.com/acm/contest/275/C
题意：
两种操作：
操作1：是求区间[L,R]的和
操作2：把[L,R]区间的每个数都异或一个数 k
最开始没反应过来，异或的和不等于和的异或，很***地写了半天。。。最会发现不会诶T_T
然后看题解，真的很厉害，他是保存每段区间内，各个位上有多少个1，然后通过这个二进制1的个数来计算贡献，也就是求和了
写给自己的：
我线段树的功底确实还很差，pushdown操作没有理解好，修改操作忘了pushdown，
修改操作pushdown是因为可能这次修改的区间是在很底下的一个区间，途中会经过以前修改的区间，所以要顺着这条路要把以前的往下推才行
比如4个数，先修改[3,4]区间，那么lazy就停在了③号节点上了，下一次要修改[3,3]区间，这段区间是在下面一层的⑥号节点，途中会经过③号节点，所以要把三号节点的信息带下去才行
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int bit=20;
LL sum[maxn<<2][bit<<1],xo[maxn<<2];
void pushup(int id)
{
for(int i=0;i<=bit;i++)
sum[id][i]=sum[id<<1][i]+sum[id<<1|1][i];
}
void Build(int id,int L,int R)
{
if(L==R)
{
int t;
scanf("%d",&t);
for(int i=0;i<=bit;i++)
{
if(t&(1<<i))sum[id][i]=1;
else sum[id][i]=0;
}
return ;
}
int mid=L+R>>1;
Build(id<<1,L,mid);
Build(id<<1|1,mid+1,R);
pushup(id);
}
void pushdown(int id,int L,int R)
{
if(xo[id])
{
xo[id<<1]^=xo[id];
xo[id<<1|1]^=xo[id];
int mid=L+R>>1;
for(int i=0;i<=bit;i++)
{
//如果这一位是1,那么异或之后0的个数和1的个数就交换
if(xo[id]&(1<<i))
{
sum[id<<1][i]=mid-L+1-sum[id<<1][i];
sum[id<<1|1][i]=R-mid-sum[id<<1|1][i];
}
}
xo[id]=0;
}
}
void Xor(int id,int L,int R,int qL,int qR,int k)
{
if(qL<=L&&qR>=R)
{
xo[id]^=k;
for(int i=0;i<=bit;i++)if(k&(1<<i))sum[id][i]=R-L+1-sum[id][i];
return ;
}
pushdown(id,L,R);
int mid=L+R>>1;
if(qL<=mid)Xor(id<<1,L,mid,qL,qR,k);
if(qR>=mid+1)Xor(id<<1|1,mid+1,R,qL,qR,k);
pushup(id);
}
LL getsum(int id)
{
LL res=0;
for(int i=0;i<=bit;i++)res+=(LL)sum[id][i]*(1LL<<i);
return res;
}
LL query(int id,int L,int R,int qL,int qR)
{
if(qL<=L&&qR>=R)return getsum(id);
pushdown(id,L,R);
int mid=L+R>>1;
LL res=0;
if(qL<=mid)res+=query(id<<1,L,mid,qL,qR);
if(qR>=mid+1)res+=query(id<<1|1,mid+1,R,qL,qR);
return res;
}
int N,Q;
void print()
{
for(int i=1;i<=4*N;i++)
{
cout<<"id="<<i<<" sum="<<sum[i]<<" xo="<<xo[i]<<" | ";
if((i&(i+1))==0)puts("");
}
puts("");
}
int main()
{
while(cin>>N>>Q)
{
memset(xo,0,sizeof xo);
Build(1,1,N);
while(Q--)
{
int cmd,L,R,k;
scanf("%d",&cmd);
if(cmd==1)
{
scanf("%d%d",&L,&R);
cout<<query(1,1,N,L,R)<<endl;
}
else
{
scanf("%d%d%d",&L,&R,&k);
Xor(1,1,N,L,R,k);
}
}
}
}
D-树上求和
https://ac.nowcoder.com/acm/contest/275/D
哇，把牛客28B的求平方和的板子套上树链剖分的板子就行了，只是我弄的时候一直WA，原因是建树的时候直接Sum1=a[L]了
代码里还有修改乘积的，懒得删了
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int MOD=23333;
int N,M,Q,R,Time,tot;
LL a[maxn];
LL dep[maxn],sz[maxn],fa[maxn];
LL top[maxn];//用来跳转到这条重链的起始节点
LL sa[maxn];//排第i个的原来是第sa[i]个节点
LL rnk[maxn];//第i个节点排rnk[i]
LL son[maxn];//保存当前节点的重节点
LL Sum1[maxn],Sum2[maxn],Add[maxn],Mul[maxn];
struct Edge
{
int t,v,nxt;
};
Edge E[maxn<<1];
int head[maxn];
void AddEdge(int aa,int bb,int val)
{
E[++tot].t=bb;
E[tot].v=val;
E[tot].nxt=head[aa];
head[aa]=tot;
}
void dfs1(int u,int pre,int deep)
{
dep[u]=deep;
fa[u]=pre;
sz[u]=1;
for(int i=head[u]; i!=-1; i=E[i].nxt)
{
int t=E[i].t;
if(t==pre)continue;
dfs1(t,u,deep+1);
sz[u]+=sz[t];
if(son[u]==-1)son[u]=t;//没有重节点
else if(sz[t]>sz[son[u]])son[u]=t;//比原来的大
}
}
void dfs2(int u,int uu)//uu为起始重节点
{
top[u]=uu;
rnk[u]=++Time;//Time为时间顺序
sa[Time]=u;
if(son[u]==-1)return ;//如果u不在重链上就不继续往下
dfs2(son[u],uu);
for(int i=head[u]; i!=-1; i=E[i].nxt)
{
int t=E[i].t;
if(t==fa[u])continue;
if(t!=son[u])dfs2(t,t);//如果不是重节点，就那么top就会变
}
}
void pushup(int id)
{
Sum1[id]=(Sum1[id<<1]+Sum1[id<<1|1])%MOD;
Sum2[id]=(Sum2[id<<1]+Sum2[id<<1|1])%MOD;
}
void pushdown(int id,int L,int R)
{
if(Add[id]!=0||Mul[id]!=1)
{
Add[id<<1] =Add[id<<1]*Mul[id]+Add[id];
Add[id<<1|1]=Add[id<<1|1]*Mul[id]+Add[id];
Mul[id<<1] *=Mul[id];
Mul[id<<1|1]*=Mul[id];
int mid=L+R>>1;
Sum2[id<<1] =Sum2[id<<1] + 2LL*Sum1[id<<1] *Add[id]%MOD + Add[id]*Add[id]%MOD*(mid-L+1)%MOD;
Sum2[id<<1|1]=Sum2[id<<1|1] + 2LL*Sum1[id<<1|1]*Add[id]%MOD + Add[id]*Add[id]%MOD*(R-mid)%MOD;
Sum1[id<<1] =Sum1[id<<1] * Mul[id]%MOD + Add[id]*(mid-L+1)%MOD;
Sum1[id<<1|1]=Sum1[id<<1|1] * Mul[id]%MOD + Add[id]*(R-mid)%MOD;
Add[id]=0;
Mul[id]=1;
Sum1[id<<1]%=MOD;Sum2[id<<1]%=MOD;Add[id<<1]%=MOD;
Sum1[id<<1|1]%=MOD;Sum2[id<<1|1]%=MOD;Add[id<<1|1]%=MOD;
}
}
void Update(int id,int L,int R,int qL,int qR,LL add,LL mul)
{
if(qL<=L&&qR>=R)
{
Add[id]=Add[id]*mul+add;
Mul[id]*=mul;
Sum2[id]=Sum2[id]+2LL*Sum1[id]*add%MOD+add*add*(R-L+1)%MOD;
Sum1[id]=Sum1[id]*mul+add*(R-L+1)%MOD;
Sum1[id]%=MOD;Sum2[id]%=MOD;Add[id]%=MOD;
return ;
}
pushdown(id,L,R);
int mid=L+R>>1;
if(qL<=mid)Update(id<<1,L,mid,qL,qR,add,mul);
if(qR>=mid+1)Update(id<<1|1,mid+1,R,qL,qR,add,mul);
pushup(id);
}
void Build(int id,int L,int R)
{
Add[id]=0;
Mul[id]=1;
if(L==R)
{
Sum1[id]=a[sa[L]]%MOD;//哇,这里直接写成了=a[L]了，一直WA
Sum2[id]=Sum1[id]*Sum1[id]%MOD;;
return ;
}
int mid=L+R>>1;
Build(id<<1,L,mid);
Build(id<<1|1,mid+1,R);
pushup(id);
}
LL query(int id,int L,int R,int qL,int qR,int cmd)
{
if(qL<=L&&qR>=R)
{
if(cmd==1)return Sum1[id];
else return Sum2[id]%MOD;
}
pushdown(id,L,R);
int mid=L+R>>1;
LL res=0;
if(qL<=mid)res+=query(id<<1,L,mid,qL,qR,cmd);
res%=MOD;
if(qR>=mid+1)res+=query(id<<1|1,mid+1,R,qL,qR,cmd);
return res%MOD;
}
void Addson(int u,LL add,LL mul)//在u节点以及他的子节点上加权值val
{
int qL=rnk[u];
int qR=rnk[u]+sz[u]-1;
Update(1,1,N,qL,qR,add,mul);
}
LL queryson(int u,int cmd)//询问u节点以及子节点的权值和
{
int qL=rnk[u];
int qR=rnk[u]+sz[u]-1;
return query(1,1,N,qL,qR,cmd);
}
int main()
{
while(cin>>N>>Q)
{
for(int i=1; i<=N; i++)
{
scanf("%lld",a+i);
a[i]%=MOD;
}
memset(head,-1,sizeof head);
memset(son,-1,sizeof son);
memset(Sum1,0,sizeof Sum1);
memset(Sum2,0,sizeof Sum2);
tot=Time=0;
for(int i=1; i<N; i++)
{
int u,v;
scanf("%d%d",&u,&v);
AddEdge(u,v,1);
AddEdge(v,u,1);
}
dfs1(1,-1,0);
dfs2(1,1);
Build(1,1,N);
while(Q--)
{
int cmd;
scanf("%d",&cmd);
if(cmd==1)
{
int u,val;
scanf("%d%d",&u,&val);
Addson(u,val%MOD,1);
}
else
{
int u;
scanf("%d",&u);
cout<<queryson(u,2)<<endl;
}
}
}
}
E-换个角度思考
https://ac.nowcoder.com/acm/contest/275/E
题解说阔以不用主席树，把询问按照右端点升序排序，然后怎么怎么操作，没怎么看懂呀T_T
离线求
反而是看了个别人的代码，他是把询问中的值 x 按照升序排列，然后看小于等于x的有在原序列里有哪些点，把这些点+1，之后树状数组就阔以快速得到有好多个
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int tree[maxn];
pair<int,int>a[maxn];
int N,Q;
void Add(int i)
{
if(i<1)return;
for(; i<maxn; i+=i&-i)tree[i]++;
}
int getsum(int i)
{
int res=0;
for(; i>0; i-=i&-i)res+=tree[i];
return res;
}
struct AAA
{
int L,R,x,id;
bool operator<(const AAA &tp)const
{
return x<tp.x;
}
};
AAA qry[maxn];
int ans[maxn];
int main()
{
while(cin>>N>>Q)
{
memset(tree,0,sizeof tree);
for(int i=1; i<=N; i++)scanf("%d",&a[i].first),a[i].second=i;
sort(a+1,a+1+N);
for(int i=1; i<=Q; i++)cin>>qry[i].L>>qry[i].R>>qry[i].x,qry[i].id=i;
sort(qry+1,qry+1+Q);
int now=1;
for(int i=1; i<=Q; i++)
{
while(now<=N && a[now].first<=qry[i].x)Add(a[now++].second);
ans[qry[i].id]=getsum(qry[i].R)-getsum(qry[i].L-1);
}
for(int i=1; i<=Q; i++)cout<<ans[i]<<endl;
}
}
主席树求
/*主席树求[L,R]内小于等于x的个数*/
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=2e6+5;
int Ls[maxn],Rs[maxn],tree[maxn];//保存左右儿子
int a[maxn],b[maxn];
vector<int>root;
int N,Q,n,tot;
int Build(int L,int R)
{
int id=++tot;
tree[id]=0;
if(L==R)return id;
int mid=L+R>>1;
Ls[id]=Build(L,mid);
Rs[id]=Build(mid+1,R);
return id;
}
void Add(int id1,int x)
{
int id2=++tot;//新建一个root
root.push_back(id2);
tree[id2]=tree[id1]+1;
int L=1,R=n;
while(L<R)
{
int mid=L+R>>1;
if(x<=mid)
{
R=mid;
Ls[id2]=++tot;
Rs[id2]=Rs[id1];
id2=tot;
id1=Ls[id1];
}
else
{
L=mid+1;
Rs[id2]=++tot;
Ls[id2]=Ls[id1];
id2=tot;
id1=Rs[id1];
}
tree[id2]=tree[id1]+1;
}
}
int query(int id,int L,int R,int x)
{
if(x>=a[R])return tree[id];
else if(x<a[L])return 0;
int res=0;
int mid=L+R>>1;
if(x<=a[mid])res+=query(Ls[id],L,mid,x);
else
{
res+=tree[Ls[id]];
res+=query(Rs[id],mid+1,R,x);
}
return res;
}
int main()
{
while(cin>>N>>Q)
{
tot=0;
memset(tree,0,sizeof tree);
root.clear();
for(int i=1; i<=N; i++)
{
scanf("%d",b+i);
a[i]=b[i];
}
sort(a+1,a+1+N);
n=unique(a+1,a+1+N)-(a+1);
root.push_back(Build(1,n));
for(int i=1; i<=N; i++)
{
int pos=lower_bound(a+1,a+1+n,b[i])-a;
Add(root[i-1],pos);
}
while(Q--)
{
int L,R,x;
scanf("%d%d%d",&L,&R,&x);
int sumR=query(root[R],1,n,x);
int sumL=query(root[L-1],1,n,x);
cout<<sumR-sumL<<endl;
}
}
}
京公网安备 11010502036488号