题意: 查询 [l,r] 子区间异或的和
题解: 按位考虑, 每一位统计奇数区间出现的次数算价值即可, 线段树区间合并
- #include <bits/stdc++.h>
- #define ll long long
- const ll mod=1e9+7;
- const int MAXN=1e5+10;
- using namespace std;
- typedef struct node{
- int len,llen,rlen,sum;ll ans;
- }node;
- node d[21][MAXN*3+10005];
- int dd[21][MAXN],a[MAXN];
- void up(int x,int pos){
- d[pos][x].ans=(d[pos][x<<1].ans+d[pos][x<<1|1].ans)%mod;
- d[pos][x].ans+=d[pos][x<<1].rlen*(d[pos][x<<1|1].len-d[pos][x<<1|1].llen);
- d[pos][x].ans%=mod;
- d[pos][x].ans+=d[pos][x<<1|1].llen*(d[pos][x<<1].len-d[pos][x<<1].rlen);
- d[pos][x].ans%=mod;
- //d[pos][x].llen=d[pos][x<<1].llen+d[pos][x<<1|1].len+d[pos][x<<1].len-d[pos][x<<1].llen+d[pos][x<<1|1].llen;
- d[pos][x].llen=d[pos][x<<1].llen;d[pos][x].rlen=d[pos][x<<1|1].rlen;
- if(d[pos][x<<1].sum%2)d[pos][x].llen+=(d[pos][x<<1|1].len-d[pos][x<<1|1].llen);
- else d[pos][x].llen+=d[pos][x<<1|1].llen;
- if(d[pos][x<<1|1].sum%2)d[pos][x].rlen+=(d[pos][x<<1].len-d[pos][x<<1].rlen);
- else d[pos][x].rlen+=d[pos][x<<1].rlen;
- d[pos][x].len=d[pos][x<<1].len+d[pos][x<<1|1].len;
- d[pos][x].sum=d[pos][x<<1|1].sum+d[pos][x<<1].sum;
- }
- void built(int rt,int l,int r,int t){
- if(l==r){d[t][rt].sum=d[t][rt].ans=d[t][rt].llen=d[t][rt].rlen=dd[t][l];d[t][rt].len=1;return ;}
- int mid=(l+r)>>1;
- built(rt<<1,l,mid,t);
- built(rt<<1|1,mid+1,r,t);
- up(rt,t);
- }
- bool flag;node ttt;
- int t1,t2;
- node merge(node x,node y){
- x.ans+=y.ans;
- x.ans+=x.rlen*(y.len-y.llen);
- x.ans+=(x.len-x.rlen)*y.llen;
- t1=x.llen;t2=y.rlen;
- if(x.sum%2)t1+=(y.len-y.llen);
- else t1+=y.llen;
- if(y.sum%2)t2+=(x.len-x.rlen);
- else t2+=x.rlen;
- x.llen=t1;x.rlen=t2;
- x.len+=y.len;x.sum+=y.sum;
- return x;
- }
- void querty(int rt,int l,int r,int ql,int qr,int t){
- if(ql<=l&&r<=qr){
- if(!flag)ttt=d[t][rt],flag=1;
- else ttt=merge(ttt,d[t][rt]);
- return ;
- }
- int mid=(l+r)>>1;
- if(ql<=mid)querty(rt<<1,l,mid,ql,qr,t);
- if(qr>mid)querty(rt<<1|1,mid+1,r,ql,qr,t);
- }
- int main(){
- int _;scanf("%d",&_);
- while(_--){
- int n,q;scanf("%d%d",&n,&q);
- for(int i=1;i<=n;i++)scanf("%d",&a[i]);
- for(int i=0;i<=20;i++){
- for(int j=1;j<=n;j++){
- if(a[j]&(1<<i))dd[i][j]=1;
- else dd[i][j]=0;
- }
- }
- for(int i=0;i<=20;i++)built(1,1,n,i);
- int l,r;ll ans=0;
- for(int i=1;i<=q;i++){
- scanf("%d%d",&l,&r);ans=0;
- for(int j=0;j<=20;j++){
- flag=0;querty(1,1,n,l,r,j);
- ans=(ans+(ttt.ans%mod)*(1<<j)%mod)%mod;
- }
- printf("%lld\n",ans);
- }
- }
- return 0;
- }
- K:
题解: 查询 [l,r] 区间里面的男生和女生是否在满足要求的情况下进行匹配, 可以通过线段树 + 双指针预处理出每个位置最小满足的右端点即可(icpc 官网上没有数据 计蒜课上的数据也是假的, 对拍了一晚上大数据感觉没啥问题)
- #include <bits/stdc++.h>
- const int MAXN=2e5+10;
- using namespace std;
- int mn[MAXN<<2],flag[MAXN<<2];
- void push(int x){
- if(flag[x]){
- mn[x<<1]+=flag[x];
- mn[x<<1|1]+=flag[x];
- flag[x<<1]+=flag[x];
- flag[x<<1|1]+=flag[x];
- flag[x]=0;
- }
- }
- void up(int x){mn[x]=min(mn[x<<1],mn[x<<1|1]);return ;}
- void built(int rt,int l,int r){
- if(l==r){mn[rt]=-1*l,flag[rt]=0;return ;}
- int mid=(l+r)>>1;
- built(rt<<1,l,mid);
- built(rt<<1|1,mid+1,r);
- up(rt);flag[rt]=0;
- }
- void update(int rt,int l,int r,int ql,int qr,int t){
- if(ql<=l&&r<=qr){mn[rt]+=t;flag[rt]+=t;return ;}
- push(rt);
- int mid=(l+r)>>1;
- if(ql<=mid)update(rt<<1,l,mid,ql,qr,t);
- if(qr>mid)update(rt<<1|1,mid+1,r,ql,qr,t);
- up(rt);
- }
- vector<int>vec;
- int a[MAXN],ans[MAXN];
- int main(){
- int _;scanf("%d",&_);
- while(_--){
- int n,m,k,t;scanf("%d%d%d",&n,&m,&k);
- for(int i=1;i<=n;i++)scanf("%d",&t),vec.push_back(t);
- sort(vec.begin(),vec.end());
- for(int i=1;i<=m;i++)scanf("%d",&a[i]);
- for(int i=1;i<=m;i++) a[i]=lower_bound(vec.begin(),vec.end(),k-a[i])-vec.begin()+1,ans[i]=m+1;
- for(int i=m+1;i<=max(n,m);i++) a[i]=n+1;
- // for(int i=1;i<=m;i++)cout<<a[i]<<" ";
- //cout<<endl;
- built(1,1,n);
- for(int i=1;i<=n;i++){
- if(a[i]>n)continue;
- update(1,1,n,a[i],n,1);
- }
- int l=1;int r=n;
- while(r<=m){
- while(r<=m&&mn[1]<0){
- r++;
- if(a[r]<=n)update(1,1,n,a[r],n,1);
- }
- if(r>m)break;
- ans[l]=r;
- //cout<<l<<" "<<ans[l]<<endl;
- if(a[l]<=n)update(1,1,n,a[l],n,-1);
- l++;
- }
- int q;scanf("%d",&q);
- for(int i=1;i<=q;i++){
- scanf("%d%d",&l,&r);
- if(ans[l]<=r)puts("1");
- else puts("0");
- }
- vec.clear();
- }
- return 0;
- }
[补题]ACM-ICPC 2017 Asia Xi'an
来源: http://www.bubuko.com/infodetail-2619073.html