F. Heroes of Making Magic III

time limit per test：3 seconds

memory limit per test：256 megabytes

input：standard input

output：standard output

I’m strolling on sunshine, yeah-ah! And doesn’t it feel good! Well, it certainly feels good for our Heroes of Making Magic, who are casually walking on a one-directional road, fighting imps. Imps are weak and feeble creatures and they are not good at much. However, Heroes enjoy fighting them. For fun, if nothing else.

Our Hero, Ignatius, simply adores imps. He is observing a line of imps, represented as a zero-indexed array of integers?a?of length?n, where?ai?denotes the number of imps at the?i-th position. Sometimes, imps can appear out of nowhere. When heroes fight imps, they select a segment of the line, start at one end of the segment, and finish on the other end, without ever exiting the segment. They can move exactly one cell left or right from their current position and when they do so, they defeat one imp on the cell that they moved to, so, the number of imps on that cell decreases by one. This also applies when heroes appear at one end of the segment, at the beginning of their walk.

Their goal is to defeat all imps on the segment, without ever moving to an empty cell in it (without imps), since they would get bored. Since Ignatius loves imps, he doesn’t really want to fight them, so no imps are harmed during the events of this task. However, he would like you to tell him whether it would be possible for him to clear a certain segment of imps in the above mentioned way if he wanted to.

You are given?q?queries, which have two types:

• 1?a?b?k?— denotes that?k?imps appear at each cell from the interval?[a,?b]
• 2?a?b?- asks whether Ignatius could defeat all imps on the interval?[a,?b]?in the way described above

Input

The first line contains a single integer?n?(1?≤?n?≤?200?000), the length of the array?a. The following line contains?n?integersa1,?a2,?...,?an?(0?≤?ai?≤?5?000), the initial number of imps in each cell. The third line contains a single integer?q?(1?≤?q?≤?300?000), the number of queries. The remaining?q?lines contain one query each. Each query is provided by integers?a,?b?and, possibly,?k(0?≤?a?≤?b?<?n,?0?≤?k?≤?5?000).

Output

For each second type of query output?1?if it is possible to clear the segment, and?0?if it is not.

Example

input 3
2 2 2
3
2 0 2
1 1 1 1
2 0 2 output 0
1

Note

For the first query, one can easily check that it is indeed impossible to get from the first to the last cell while clearing everything. After we add 1 to the second position, we can clear the segment, for example by moving in the following way:?.

Solution

題目大意：

給定區(qū)間[0,N-1]，支持兩種操作：

1.區(qū)間[l,r]權(quán)值+K

2.區(qū)間是否可以刪光（這里移動(dòng)時(shí)不允許移動(dòng)到區(qū)間之外）

這里可以刪光的含義是：從一個(gè)格，可以向左/右移動(dòng)一格，每移動(dòng)一步，必須使左/右權(quán)值-1，當(dāng)一個(gè)地方權(quán)值為0時(shí)，無法向其移動(dòng)，刪光即能否按照這種移動(dòng)方式將這個(gè)區(qū)間中的所有權(quán)值刪光。

區(qū)間上的問題顯然可以考慮用線段樹來實(shí)現(xiàn)。

問題在于這種移動(dòng)方式，我們不妨考慮其性質(zhì)。

對(duì)于詢問一個(gè)區(qū)間是否能刪光，不同的移動(dòng)方法都有可能能完成，但為了方便我們只考慮其中一種方法。

對(duì)于區(qū)間$[l,r]$我們從$l$開始移動(dòng)，我們就先在$l$和$l+1$之間來回，直到$l$清空，我們再在$l+1$和$l+2$之間來回，直到$l+1$清空，如此直到$r-1$和$r$

那么這樣能夠清空所有位置的權(quán)值的條件是：

$$a_{l}>=1$$

$$a_{l+1}-a_{l}>=0$$

$$a_{l+2}-(a_{l+1}-a_{l}+1)>=0$$

$$......$$

那么我們化簡一下所有的式子可以得到：

$$a_{l}>=1$$

$$a_{l+1}-a_{l}>=0$$

$$a_{l+2}-a_{l+1}+a_{l}>=1$$

$$......$$

觀察一下不等式右邊，發(fā)現(xiàn)和項(xiàng)數(shù)的奇偶有關(guān)。

那么我們就可以得到一個(gè)通式：

$$a_{r}-a{r-1}+a{r-2}-a_{r-3}+...a_{l}>=[(r-l+1)mod1==0] $$

然后我們很直觀的想法就是用線段樹去維護(hù)這個(gè)東西，并且能分奇偶維護(hù)更加方便。

問題在于如何維護(hù)這個(gè)東西，我們做差，另$d_{i}=a_{1}-a{2}+a{3}...$

我們就可以利用這個(gè)東西，計(jì)算一個(gè)區(qū)間的值。 所以我們用線段樹去維護(hù)這個(gè)東西。

對(duì)于一個(gè)區(qū)間$[l,r]$這個(gè)區(qū)間的值$D[l,r]$可以通過$d$來計(jì)算

然后我們按照奇偶分別維護(hù)，就可以了。

Code

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; #define LL long long inline int read() {int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } #define MAXN 300010 #define INF 0x7fffffff int N,Q,a[MAXN],d[MAXN]; namespace SegmentTree {struct SegmentTreeNode{int l,r,size; LL sum,tag[2],D[2]; bool f;}tree[MAXN<<2];#define ls now<<1#define rs now<<1|1inline void Update(int now,bool o){tree[now].D[0]=min(tree[ls].D[0],tree[rs].D[o]);tree[now].D[1]=min(tree[ls].D[1],tree[rs].D[o^1]);}inline void PushDown(int now,bool o){if (tree[now].l==tree[now].r) return;if (tree[now].tag[0])tree[ls].D[0]+=tree[now].tag[0],tree[ls].tag[0]+=tree[now].tag[0],tree[rs].D[o]+=tree[now].tag[0],tree[rs].tag[o]+=tree[now].tag[0],tree[now].tag[0]=0;if (tree[now].tag[1])tree[ls].D[1]+=tree[now].tag[1],tree[ls].tag[1]+=tree[now].tag[1],tree[rs].D[o^1]+=tree[now].tag[1],tree[rs].tag[o^1]+=tree[now].tag[1],tree[now].tag[1]=0;}inline void BuildTree(int now,int l,int r){tree[now].l=l; tree[now].r=r; tree[now].size=r-l+1;if (l==r) {tree[now].D[0]=d[l]; tree[now].D[1]=INF; return;}int mid=(l+r)>>1;BuildTree(ls,l,mid); BuildTree(rs,mid+1,r);Update(now,tree[ls].size&1);}inline void Modify(int now,int L,int R,LL x,bool o){ if (L>R) return;int l=tree[now].l,r=tree[now].r;PushDown(now,tree[ls].size&1);if (L<=l && R>=r) {tree[now].tag[o]+=x; tree[now].D[o]+=x; return;}int mid=(l+r)>>1;if (L<=mid) Modify(ls,L,R,x,o);if (R>mid) Modify(rs,L,R,x,o^(tree[ls].size&1));Update(now,tree[ls].size&1);}inline LL Query(int now,int L,int R,bool o){if (L>R) return INF;int l=tree[now].l,r=tree[now].r;PushDown(now,tree[ls].size&1);if (L<=l && R>=r) return tree[now].D[o];int mid=(l+r)>>1; LL re=INF;if (L<=mid) re=min(re,Query(ls,L,R,o));if (R>mid) re=min(re,Query(rs,L,R,o^(tree[ls].size&1)));return re;} } using namespace SegmentTree; int main() {N=read();for (int i=0; i<=N-1; i++) a[i]=read();d[0]=a[0]; for (int i=1; i<=N-1; i++) d[i]=a[i]-a[i-1],a[i]-=a[i-1];SegmentTree::BuildTree(1,0,N-1);Q=read();while (Q--){int opt=read(),L=read(),R=read(),K;if (opt==1){K=read(); SegmentTree::Modify(1,L,R,K,L&1);if ((R-L+1)&1) SegmentTree::Modify(1,R+1,N-1,-K,(R+1)&1),SegmentTree::Modify(1,R+2,N-1,K,(R+2)&1);}if (opt==2){LL x=L>0? SegmentTree::Query(1,L-1,L-1,(L-1)&1):0,y=SegmentTree::Query(1,R,R,R&1);if ((R-L+1)&1) y+=x; else y-=x;if (y!=((R-L+1)&1) || SegmentTree::Query(1,L,R,L&1)+x<1 || SegmentTree::Query(1,L,R,(L&1)^1)-x<0) puts("0");else puts("1");} // puts("========================="); // for (int i=0; i<=N-1; i++) printf("%I64d %I64d\n",Query(1,i,i,i&1),Query(1,i,i,(i&1)^1)); // puts("========================="); }return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5919044.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【Codeforces717F】Heroes of Making Magic III 线段树 + 找规律的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。