题目描述
作为一名新世纪共产主义的接班人，你认识到了资本主义的软弱性与妥协性，决定全面根除资本主义，跑步迈入共产主义。但是当你即将跨入共产主义大门的时候，遇到了万恶的资本家留下的与非电路封印，经过千辛万苦的研究，你终于把复杂的破解转变成了以下问题：
初始时你有一个空序列，之后有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)
输出
输出到nand.out中。
输出有多行。为对于每一个操作二的回答。
样例输入
6
1 1
1 1
1 0
2 1 2
2 1 3
2 2 3
样例输出
1
0
0
【数据规模和约定】
数据点 N的规模 操作一的个数M1 操作二的个数M2
1 N<=1000 M1<=500 M2<=500
2 N<=1000 M1<=500 M2<=500
3 N<=200000 M1<=100000 M2<=100000
4 N<=200000 M1<=100000 M2<=100000
5 N<=1000000 M1<=900000 M2<=100000
N<=4000000 M1<=3900000 M2<=100000
题解
想了好久 也没想出来
最后放弃了
其实可以分类讨论
最后会发现一个结论
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
inline int read()
{
int s = 0, k = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
k = ch == '-' ? -1 : k, ch = getchar();
while (ch >= '0' && ch <= '9')
s = s * 10 + (ch ^ 48), ch = getchar();
return s * k;
}
int n;
bool Sum[4000005];
bool f[4000005];
bool a[4000005];
int main()
{
n = read();
int t = 0, op, l, r;
int lastans = 0;
while (n--)
{
op = read();
if (op == 1)
{
l = read() ^ lastans;
t++;
a[t] = l;
if (t == 1)
f[t] = a[t];
else
f[t] = !(f[t - 1] & l);
Sum[t] = Sum[t - 1] ^ f[t];
}
else
{
l = read(), r = read();
if (lastans)
{
l = t - l + 1;
r = t - r + 1;
swap(l, r);
}
lastans = a[l];
int i = l, now = !(a[l] & a[l + 1]);
while (now != f[i + 1] && i < r)
{
lastans ^= now;
i++;
now = !(now & a[i + 1]);
}
if (i < r)
{
lastans ^= Sum[r] ^ Sum[i];
}
printf("%d\n", lastans);
}
}
//while (1);
}