作为一名新世纪共产主义的接班人,你认识到了资本主义的软弱性与妥协性,决定全面根除资本主义,跑步迈入共产主义。但是当你即将跨入共产主义大门的时候,遇到了万恶的资本家留下的与非电路封印,经过千辛万苦的研究,你终于把复杂的破解转变成了以下问题:
初始时你有一个空序列,之后有 N 个操作。
操作分为一下两种:
1 x:在序列末尾插入一个元素 x(x=0 或 1)。
2 L R:定义 nand[L,R] 为序列第 L 个元素到第 R 个元素的与非和,询问 nand[L,L]^nand[L,L+1]^nand[L,L+2]^......^nand[L,R]。
Nand 就是先与,再非
从文件 nand.in 中读入数据。
输入第一行一个正整数 N,表示操作个数。
接下来 N 行表示 N 个操作。
为了体现程序的在线性,记 lastans 为上一次操作二的回答,初始 lastans=0,。对于操作 1,你需要对 x 异或 lastans。对于操作二,设现在序列中的元素个数为 M,如果 lastans=1,那么你需要作如下操作:L=M-L+1,R=M-R+1,swap(L,R)
【数据规模和约定】
N<=4000000 M1<=3900000 M2<=100000
先吐槽一下题目描述,上面的题目是我自己矫正过的,原来题目就卡死了无数人,连样例都搞不出来。
这道题先膜拜一下 Troywar 大犇,成功通过理性分析与令人窒息的操作强行干过这道题,成功蔑视了数据和出题人的智商。因此我今天就讲一下撸串神的比正解快出去无数倍的 "非正解"。
首先,先设定 f[i] 为 nand[1,i],所以 f[i] 的通项公式就明了了 f[i+1]=!(f[i]&a[i+1]),nand[i,i+1]=!(a[i]&a[i+1]),nand[i+2]=!(nand[i+1]&a[i+2]),que[i,j]=a[i]^nand[i+1]^nand[i+2]……
那我们先观察一下 f[i+1] 和 nand[i,i+1], 可以发现,若 a[i+1]=0 那么两式相等,使 nand[i+2]=f[i+2],以此类推,可以发现只要有零出现,后方的 f[i] 一定等于 nand[i],一次对于每一次讯问我们只要先暴力找一下第一个为零或直接找 f[i] 与 nand[i] 相等的地方就可以,后面 f[i] 与 nand[i] 都相等了,因此只要再去维护一个前缀 f[i] 的异或和即可,找到 0 后直接将数据分开处理,在 0 左方直接暴力,在 0 右方(包括 0 位),用前缀和搞。
可能很多人会有疑惑,这样不会超时吗,当然不会,首先,通过本题的题目描述可以推断,他一定不是先添加完再询问,应当是添加完一点再去询问几次,这样,由于他的强制在线,出现 0 的几率是相当大的,因此不会超时,实在担心的话也可以记录一下 0 的出现次数的前缀和,然后再去二分查找。
- #include<iostream>
- #include<cstdlib>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<map>
- #include<queue>
- #include<string>
- #include<cmath>
- using namespace std;
- int n,la,zz;
- int a[4000005];
- int f[4000005];
- int sum[4000005];
- int nand(int x,int y){
- return (!(x&y));
- }
- int na[50];
- int su[4000005][2];
- int main(){
- // freopen("nand.in","r",stdin);
- // freopen("nand.out","w",stdout);
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- int z;
- scanf("%d",&z);
- if(z==1)
- {
- int x;
- scanf("%d",&x);
- x^=la;
- zz++;
- a[zz]=x;
-
- f[zz]=nand(f[zz-1],a[zz]);
- sum[zz]=sum[zz-1]^f[zz];
-
- su[zz][0]=su[zz-1][0];
- su[zz][1]=su[zz-1][1];
-
- su[zz][x]++;
- }
- else
- {
- int x,y;
- scanf("%d%d",&x,&y);
- if(la)
- {
- x=zz-x+1;
- y=zz-y+1;
- swap(x,y);
- }
- int cnt=a[x],bj=0,sm=a[x];
- for(int i=x+1;i<=y;i++)
- {
- sm=nand(sm,a[i]);
- if(sm==f[i])
- {
- bj=i;
- break;
- }
- cnt^=sm;
- }
- if(bj) cnt^=sum[y]^sum[bj-1];
- la=cnt;
- printf("%d\n",la);
- }
- }
- // while(1);
- return 0;
- }
View Code