Fork me on GitHub

Codeforces717F

Codeforces717F题解

题解:

  • 以下根据网上大佬们的博客。
  • 消除完一个区间肯定有一大堆方法,不妨考虑其中一种:
  • 先前两个之间反复横跳,消除光第一个,然后再消除第二个,直到消除完。
  • 然后我们可以根据这个列出不等式和方程:
  • 然后我们令$d_i=a_i-a_{i-1}+\cdots$,用线段树维护即可。

代码:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define inf 1e9
#define N 200009
#define mid (l+r>>1)
#define root 1,1,n
#define lc cur<<1
#define rc lc|1
#define lson lc,l,mid
#define rson rc,mid+1,r
#define now cur,l,r
using namespace std;
int n,m,a[N],bit[N],b[N],tg[N<<2][2],Min[N<<2][2];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
void up(int cur,int l,int r)
{
Min[cur][0]=min(Min[lc][0],Min[rc][0]);
Min[cur][1]=min(Min[lc][1],Min[rc][1]);
}
void down(int cur,int l,int r)
{
for (int k=0;k<2;k++)
if (tg[cur][k])
{
tg[lc][k]+=tg[cur][k],tg[rc][k]+=tg[cur][k];
Min[lc][k]+=tg[cur][k],Min[rc][k]+=tg[cur][k];
tg[cur][k]=0;
}
}
void build(int cur,int l,int r)
{
if (l==r)
{
Min[cur][l&1]=b[l];
Min[cur][l&1^1]=inf;
tg[cur][0]=tg[cur][1]=0;
return;
}
build(lson);
build(rson);
up(now);
}
void ins(int cur,int l,int r,int L,int R,int y,int k)
{
if (L>R) return;
if (L<=l&&R>=r)
{
tg[cur][k]+=y;
Min[cur][k]+=y;
return;
}
down(now);
if (L<=mid) ins(lson,L,R,y,k);
if (R>mid) ins(rson,L,R,y,k);
up(now);
}
int qry(int cur,int l,int r,int L,int R,int k)
{
if (L<=l&&R>=r) return Min[cur][k];
down(now);
int ret=inf;
if (L<=mid) ret=min(ret,qry(lson,L,R,k));
if (R>mid) ret=min(ret,qry(rson,L,R,k));
return ret;
}
int qry(int cur,int l,int r,int x,int k)
{
if (x==0) return 0;
if (l==r) return Min[cur][k];
down(now);
if (x<=mid) return qry(lson,x,k);
else return qry(rson,x,k);
}
int main()
{
n=read();
for (int i=1;i<=n;i++) a[i]=read();
m=read();
for (int i=1;i<=n;i++) b[i]=a[i]-b[i-1];
build(root);
while (m--)
{
int op=read();
if (op==1)
{
int l=read()+1,r=read()+1,k=read();
ins(root,l,r,k,l&1);
if ((r-l+1)&1) ins(root,r+1,n,k,l&1),ins(root,r+1,n,-k,l&1^1);
}
else
{
int l=read()+1,r=read()+1;
if ((r-l+1)&1)
{
int ret=qry(root,l-1,(l-1)&1);
int ret1=qry(root,l,r,r&1)+ret;
int ret2=qry(root,l,r,r&1^1)-ret;
int ret3=qry(root,r,r&1)+ret;
if (ret3==1&&ret1>=1&&ret2>=0) puts("1");
else puts("0");
}
else
{
int ret=qry(root,l-1,(l-1)&1);
int ret1=qry(root,l,r,r&1)-ret;
int ret2=qry(root,l,r,r&1^1)+ret;
int ret3=qry(root,r,r&1)-ret;
if (ret3==0&&ret1>=0&&ret2>=1) puts("1");
else puts("0");
}
}
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces717F

文章作者:wzf2000

发布时间:2017年12月26日 - 10:12

最后更新:2017年12月26日 - 10:12

原始链接:https://wzf2000.github.io/2017/12/26/Codeforces717F/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。