【学员专栏012期】题解 P5523 【[yLOI2019] 珍珠】-黄子睿
作者：黄子睿
ID：huangzirui
学校：长沙市中雅培粹新九年级
获奖：2019年提高组一等奖，普及组一等奖（满分）
博客地址：https://www.luogu.com.cn/blog/My-luoguBuoke-HZR/solution-p5523
题意：
定义运算 nand （ 非与 ）为：
A nand B =not(A and B)
即：
| nand | 0 | 1 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 0 |
现在给你一个序列 A，要你支持以下操作：
从序列的左边或右边插入一个非 0 即 1 的数。
从序列的左边或右边开始，查询连续 x 个数的 非与 值
操作数 ≤10^7+6
（吐槽：原题输入格式太 duliu 了）
首先找一下 nand 操作有什么性质。
发现 0 nand 任何一个数都是 1 。
这意味着无论有多少个数做这个运算，只要运算的过程中有 0 ，那么不论前面有什么东西，到这个位置统统都变成 1 ，所以答案只和 0 后面的有关。（这意味着答案只和最后的 0 有关）
那么假如我们从右往左查询，我们只需要找到查询到的最后一个数，再从这个节点往前找到一个 0 ，最后计算从这个 0 到最后一个数的答案即可。
比如：
A = 1,0,1,0,1,1,1,1,0
我现在想从左往右查询 8 个数，那么查询到的最后一个数就是第八个数。第八个数左边的第一个 0 在第四个位置。然后从第四个位置向右 非与 即可。
又因为这样子计算相当于计算 1nand 1 nand 1 … nand 1 。这个表达式的值显然可以 O(1) 计算。
所以原问题就转化成求一个位置上向左和向右的第一个 0 的位置。又因为这道题插入的方式很奇特，这个东西可以从上一个数递推过来（也可以从新加入的数推过来）。具体的说：
设第 i 个位置向左第一个 0 的位置为 Li ，向右第一个位置是 Ri
当我们从左边加了一个 0 ，那就可以把这个 0 右边所有连续的 1 的 L 数组都设成这个位置。又因为每个 0 最多被一个 1 查找到，均摊复杂度是 O( 长度 ) 的。
当我们从左边加了一个 1 ， Ri可以直接从 R(i+1)处得到。
然后算法大概分析完了。
这道题细节相当多，比如 0 nand 一个数答案肯定是 1 ，但是它单独一个数时就是 0 ，因此要特判一开始就是 0 的情况。
代码主体部分不长，输入部分占了一半，果然是输入格式防 AK 题。
#include <bits/stdc++.h>using namespace std;
namespace Maker {
typedef unsigned int uit;
bool __sp;uit __x, __y, __z;int __type, __k, __m;
const int L = 1 << 21;char buf[L], *front=buf, *end=buf;char GetChar() { if (front == end) { end = buf + fread(front = buf, 1, L, stdin); if (front == end) return -1; } return *(front++);}
template <typename T>inline void qr(T &x) { char ch = GetChar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch = GetChar(); while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = GetChar(); if (lst == '-') x = -x;}
template <typename T>inline void Begin(const T &x) { __type = x % 10; qr(__x); qr(__y); qr(__z); qr(__m); __sp = (__type == 3) || (__type == 4); __type &= 1;}
inline uit __Next_Integer() { __x ^= __y << (__z & 31); __y ^= __z >> (__x & 31); __z ^= __x << (__y & 31); __x ^= __x >> 5; __y ^= __y << 13; __z ^= __z >> 6; return __x;}
inline uit Rand() { return __Next_Integer(); }
template <typename Tx, typename Ty, typename Tz>inline void Get_Nextline(Tx &x, Ty &y, Tz &z) { if (__m) { --__m; x = 0; y = 0; z = 0; qr(x); qr(y); qr(z); if (x == 0) ++__k; } else { x = Rand() & 1; y = Rand() & 1; if (__k == 0) { x = 0; } if (x == 0) { ++__k; if (__sp) { z = __type; } else { z = Rand() & 1; } } else { int dk = __k >> 1; if (dk == 0) { z = 1; } else { z = Rand() % dk + dk; } } }}}
const int maxn=3e7+10;
int Left[maxn],Right[maxn];int nowL=15000001,nowR=15000000;int i,j,k,n,m;int ans1,ans2,ans3,ans4;
int main() { scanf('%d', &n); Maker::Begin(n); memset(Left,-1,sizeof(Left)); memset(Right,-1,sizeof(Right)); int id=0; for (int x,y,z;n;--n){ ++id; int ans=-1; Maker::Get_Nextline(x, y, z); if(x==0 && y==0 && z==1){ nowL--; Left[nowL]=-1; Right[nowL]=Right[nowL+1]; }if(x==0 && y==0 && z==0){ nowL--; Left[nowL]=nowL; Right[nowL]=nowL; for(i=nowL+1;i<=nowR;i++){ if(Left[i]!=-1)break; Left[i]=nowL; } } if(x==0 && y==1 && z==1){ nowR++; Right[nowR]=-1; Left[nowR]=Left[nowR-1]; }if(x==0 && y==1 && z==0){ nowR++; Right[nowR]=nowR; Left[nowR]=nowR; for(i=nowR-1;i>=nowL;i--){ if(Right[i]!=-1)break; Right[i]=nowR; } } int Z=-1; if(x==1 && y==0){ z=z+nowL-1; Z=Left[z]; if(z==nowL){ if(Left[z]==-1)ans=1; else ans=0; }else{ if(Z==nowL)Z--; if(Z==-1)Z=nowL; if((z-Z)%2==0)ans=1; else ans=0; } } if(x==1 && y==1){ z=nowR-z+1; Z=Right[z]; if(z==nowR){ if(Right[z]==-1)ans=1; else ans=0; }else{ if(Z==nowR)Z++; if(Z==-1)Z=nowR; if((Z-z)%2==0)ans=1; else ans=0; } } if(ans==1)ans1++; if(ans==0 && id%2==1)ans2++; if(ans==1 && id%2==0)ans3++; if(ans==0 && id%1024==0)ans4++; }cout<<ans1<<' '<<ans2<<' '<<ans3<<' '<<ans4<<endl; return 0;}