为什么add要先更新答案后更新桶呀,初学莫队求解答

P4462 [CQOI2018] 异或序列

@[Mon3_ter](/user/1025259) 因为你一开始设定的l=r+1,假如询问为:1,1;lr一开始为1,0,则你add的时候会更新r(r+1),而你下标是从1开始的,你更新的是下标为1的情况(++r的情况),而不是下标为0的情况(r++)。 简单来说,就是你add的时候的lr指针所指的地方被更新过了或者根本没有东西要更新;del的时候lr删掉的东西是lr指的地方(这个地方已经被更新了,不需要考虑错误),而不是减(加)了之后的所指的地方。 如果你不想add先更新再改,你可以初始l=0,r=0,拓展(收缩)的时候改一下就行。
by harmis_yz @ 2023-08-13 22:29:22


@[harmis_yz](/user/993404) ```cpp #include<bits/stdc++.h> using namespace std; const int N=1e5+5; #define ll long long ll sz,n,m,k,sum=0,b[N*2],a[N],ans[N]; struct node{ ll l,r,id; bool operator < (node x){ if(l/sz==x.l/sz) return r<x.r; else return l<x.l; } }mo[N]; void add(ll x){ sum+=b[a[x]^k]; ++b[a[x]]; } void del(ll x){ b[a[x]]--; sum-=b[a[x]^k]; } int main(){ std::ios::sync_with_stdio(false); cin>>n>>m>>k;sz=pow(n,2.0/3.0); for(int i=1;i<=n;i++) cin>>a[i],a[i]^=a[i-1]; ll ql,qr; for(int i=1;i<=m;i++){ cin>>ql>>qr; mo[i].l=ql-1;mo[i].r=qr;mo[i].id=i; } sort(mo+1,mo+m+1);b[0]=1; ll l=0,r=0; for(int i=1;i<=m;i++){ node &q=mo[i]; while(l<q.l) del(l++); while(l>q.l) add(--l); while(r<q.r) add(++r); while(r>q.r) del(r--); ans[q.id]=sum; } for(int i=1;i<=m;i++) cout<<ans[i]<<endl; } ```
by Kopicy_sama @ 2023-08-13 23:09:07


以上是ac代码加入调换add内顺序就会被俩组数据hack
by Kopicy_sama @ 2023-08-13 23:09:59


@[Mon3_ter](/user/1025259) ……,我不是这个意思,你这种顺序可以上oiwiki找找,好像不能用这种
by harmis_yz @ 2023-08-14 08:01:54


@[Mon3_ter](/user/1025259) 详见我的题解,讲得很清楚(为什么有题解不看啊
by Deamer @ 2023-08-23 13:54:33


@[Kopicy_sama](/user/1025259) 方舟人好强,这么有实力
by ReturnOrContinue @ 2023-11-15 19:12:53


|