别叹息太多告别，至少相遇很真切。
摇曳着盛放枯竭，时间从未停歇。
天涯浪迹的白雪，念念不忘山川蝴蝶。
听说有人孤负黑夜，偏要点亮人间的月。
简要题意
定义运算 为 ， 指按位与， 指按位取反。你需要动态维护一个数列，支持在前端插入，后端插入，询问一段前缀或后缀的 和，保证在任意时刻数列中只有 和 。
思路
此处仅介绍前缀的做法，后缀与前缀维护方式相同。
的运算表：
容易发现，当参与运算的两个数字中只要有 那么运算结果必为 。所以当询问的前缀最后一个数字为 时，必然结果为 。而如果是 ，由于任意一段以 结尾的前缀的 和必为 。则只需计算在这个数字前面离这个数字最近的一个 到这个数字的 和。这是一段全 段。全 段的运算结果与 的个数奇偶性相关。考虑对于每个 维护 表示第 个位置距前面最近一个 的距离，初始时 为 表示前面没有 。
往后插入一个数的时候，当这个数为 时更新 。设插入的位置为 ，检查前面一个数，如果前面为 ， 赋为 。否则按照 更新 。
往前插入一个数的时候，这个数为 时直接把 赋为 ，若为 ，则向后遍历每个值为 并且 为 的位置，更新这些位置的 值。每个数字最多被离其最近的前面的 更新一次，均摊时间复杂度 。
注意特判 在第一个数时的情况，没有进行 运算，值为 。
设有 次操作，时间复杂度为 。
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;
}
CPP
|