与非 - NekoMio's Blog

题目描述#

作为一名新世纪共产主义的接班人，你认识到了资本主义的软弱性与妥协性，决定全面根除资本主义，跑步迈入共产主义。但是当你即将跨入共产主义大门的时候，遇到了万恶的资本家留下的与非电路封印，经过千辛万苦的研究，你终于把复杂的破解转变成了以下问题：

初始时你有一个空序列，之后有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);
}