别叹息太多告别，至少相遇很真切。
摇曳着盛放枯竭，时间从未停歇。
天涯浪迹的白雪，念念不忘山川蝴蝶。
听说有人孤负黑夜，偏要点亮人间的月。
简要题意
定义运算 $a \operatorname{nand} b$ 为 $\operatorname{not}(a \operatorname{and} b)$，$\operatorname{and}$ 指按位与，$\operatorname{not}$ 指按位取反。你需要动态维护一个数列，支持在前端插入，后端插入，询问一段前缀或后缀的 $\operatorname{nand}$ 和，保证在任意时刻数列中只有 $0$ 和 $1$。
思路
此处仅介绍前缀的做法，后缀与前缀维护方式相同。
$\operatorname{nand}$ 的运算表：
| $\bf{nand}$ | $\bf{0}$ | $\bf{1}$ |
|---|
| $0$ | $1$ | $1$ |
| $1$ | $1$ | $0$ |
容易发现，当参与运算的两个数字中只要有 $0$ 那么运算结果必为 $1$。所以当询问的前缀最后一个数字为 $0$ 时，必然结果为 $1$。而如果是 $1$，由于任意一段以 $0$ 结尾的前缀的 $\operatorname{nand}$ 和必为 $1$。则只需计算在这个数字前面离这个数字最近的一个 $0$ 到这个数字的 $\operatorname{nand}$ 和。这是一段全 $1$ 段。全 $1$ 段的运算结果与 $1$ 的个数奇偶性相关。考虑对于每个 $1$ 维护 $dis_i$ 表示第 $i$ 个位置距前面最近一个 $0$ 的距离，初始时 $dis_i$ 为 $-1$ 表示前面没有 $0$。
往后插入一个数的时候，当这个数为 $1$ 时更新 $dis$。设插入的位置为 $i$，检查前面一个数，如果前面为 $0$，$dis_i$ 赋为 $1$。否则按照 $dis_{i-1}$ 更新 $dis_i$。
往前插入一个数的时候，这个数为 $1$ 时直接把 $dis_1$ 赋为 $-1$，若为 $0$，则向后遍历每个值为 $1$ 并且 $dis$ 为 $-1$ 的位置，更新这些位置的 $dis$ 值。每个数字最多被离其最近的前面的 $0$ 更新一次，均摊时间复杂度 $O(1)$。
注意特判 $0$ 在第一个数时的情况，没有进行 $\operatorname{nand}$ 运算，值为 $0$。
设有 $n$ 次操作，时间复杂度为 $O(n)$。
Code
合理使用封装可以简化代码。此份代码省略题面提供的数据生成器。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include<cstdio>
#include<iostream>
namespace lly
{
using namespace std;
constexpr int N=1e7+11;
struct deque
{
int a[N<<1],dis[N<<1],p1=N,p2=N;
inline void push_back(int x)
{
++x;
a[++p2]=x;
if(a[p2]==1)return;
if(a[p2-1]==2)dis[p2]=((dis[p2-1]==-1)?-1:(dis[p2-1]+1));
else dis[p2]=(p2==p1+1?-1:0);
}
inline void push_front(int x)
{
++x;
a[p1--]=x;
if(a[p1+1]==1) for(int i=p1+2;i<=p2&&a[i]==2;i++)dis[i]=i-p1-2;
else dis[p1+1]=-1;
}
inline int query(int x)
{
if(a[p1+x]==1) return x!=1;
if(dis[p1+x]==-1) return x&1;
if(dis[p1+x]==x-2) return (dis[p1+x]&1)^1;
return dis[p1+x]&1;
}
}o,r;
namespace collect
{
int s1=0,s2=0,s3=0,s4=0;
inline void put(int id,int x)
{
if(x)++s1;
if((id&1)&&!x)++s2;
if(!(id&1)&&x)++s3;
if(!(id&1023)&&!x)++s4;
}
inline void out(){cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<"\n";}
}
inline void work()
{
int n;scanf("%d",&n);
Maker::Begin(n);
for(int i=1;i<=n;i++)
{
int x,y,z;Maker::Get_Nextline(x,y,z);
if(x==0)
{
if(y==0) o.push_front(z),r.push_back(z);
else o.push_back(z),r.push_front(z);
}
else
{
int ans;
if(y==0) ans=o.query(z);
else ans=r.query(z);
collect::put(i,ans);
}
}
collect::out();
}
}
int main()
{
#ifdef llydebug
freopen(".in","r",stdin);
#endif
lly::work();
return 0;
}
|