并不对劲的复健训练-bzoj5301:loj2534:p4462 [CQOI2018]异或序列

àì夳堔傛蜴生んèń 2023-08-17 16:46 42阅读 0赞

##### 题目大意 #####

给出一个序列\\(a\_1,...,a\_n\\)(\\(a,n\\leq 10^5\\))，一个数\\(k\\)(\\(k\\leq 10^5\\))，\\(m\\)(\\(m\\leq10^5\\))次询问，每次询问给\\(l,r\\)，求\\(\[l,r\]\\)有多少个子区间\\(\[x,y\]\\)满足\\(a\_x \\bigoplus ...\\bigoplus a\_y=k\\)

##### 题解 #####

求前缀异或和\\(s\_1,...,s\_n\\)，询问变成对于每个\\(x\\in \[l,r\]\\)，总共有多少\\(y\\in\[l-1,x)\\)满足\\(a\_x\\bigoplus a\_y=k\\)，即询问有多少个\\(y\\in\[l-1,x)\\)满足\\(a\_x\\bigoplus k=a\_y\\)  
这样就会有一个暴力的想法：从\\(l\\)到\\(r\\)枚举\\(x\\)，维护\\(a\_\{l-1\},...,a\_\{x-1\}\\)中每个值的出现次数。  
发现\\(k\\)不变，没有修改或强制在线，就可以考虑离线。  
假设当前考虑的区间是\\(\[l\_0,r\_0\]\\)，把区间变成\\(\[l\_0-1,r\_0\]\\)时要考虑\\(a\_\{l\_0-2\}\\)与\\(a\_\{l\_0-1\},...,a\_\{r\_0\}\\)的贡献。把区间变成\\(\[l\_0+1,r\_0\]\\)时同理。  
假设当前考虑的区间是\\(\[l\_0,r\_0\]\\)，把区间变成\\(\[l\_0,r\_0+1\]\\)时要考虑\\(a\_\{r\_0+1\}\\)与\\(a\_\{l\_0-1\},...,a\_\{r\_0\}\\)的贡献。把区间变成\\(\[l\_0,r\_0-1\]\\)时同理。

##### 代码 #####

#include<algorithm>
    #include<bitset>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];k!=-1;k=nxt[k])
    #define maxn 100007
    #define maxk ((1<<17)+1)
    #define LL long long
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(LL x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    int blo=300,num[maxk],num2[maxk],a[maxn],n,m,k;
    LL ans[maxn],nowans;
    struct quest{int l,r,id;}q[maxn];
    bool cmp(quest x,quest y){return (x.l/blo==y.l/blo)?(x.r<y.r):(x.l<y.l);}
    void addl(int id,int f)
    {
        if(f==1)num2[a[id]]++;
        nowans+=(LL)f*num2[a[id-1]^k];
        if(f==-1)num2[a[id]]--;
        num[a[id-1]]+=f;
    }
    void addr(int id,int f)
    {
        if(f==1)num[a[id-1]]++;
        nowans+=(LL)f*num[a[id]^k];
        if(f==-1)num[a[id-1]]--;
        num2[a[id]]+=f;
    }
    int main()
    {
        n=read(),m=read(),k=read();
        rep(i,1,n)a[i]=a[i-1]^read();
        rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;//cout<<"ookk"<<endl;
        sort(q+1,q+m+1,cmp);
        int nowl=1,nowr=1;num[0]++,num2[a[1]]++,nowans+=(k==a[1])?1:0;
        rep(i,1,m)
        {
            while(nowl>q[i].l)nowl--,addl(nowl,1);
            while(nowr<q[i].r)nowr++,addr(nowr,1);
            while(nowl<q[i].l)addl(nowl,-1),nowl++;
            while(nowr>q[i].r)addr(nowr,-1),nowr--;
            ans[q[i].id]=nowans;
        }
        //rep(i,1,n)cout<<a[i]<<" ";cout<<endl;
        //rep(i,1,n)cout<<b[i]<<" ";cout<<endl;
        rep(i,1,m)write(ans[i]);
        return 0;
    }

##### 一些感想 #####

想玩飞天虫棍！！！

转载于:https://www.cnblogs.com/xzyf/p/11532923.html