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

題目大意：

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

1.區間[l,r]權值+K

2.區間是否可以刪光（這里移動時不允許移動到區間之外）

這里可以刪光的含義是：從一個格，可以向左/右移動一格，每移動一步，必須使左/右權值-1，當一個地方權值為0時，無法向其移動，刪光即能否按照這種移動方式將這個區間中的所有權值刪光。

區間上的問題顯然可以考慮用線段樹來實現。

問題在于這種移動方式，我們不妨考慮其性質。

對于詢問一個區間是否能刪光，不同的移動方法都有可能能完成，但為了方便我們只考慮其中一種方法。

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

那么這樣能夠清空所有位置的權值的條件是：

$$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$$

$$......$$

觀察一下不等式右邊，發現和項數的奇偶有關。

那么我們就可以得到一個通式：

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

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

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

我們就可以利用這個東西，計算一個區間的值。 所以我們用線段樹去維護這個東西。

對于一個區間$[l,r]$這個區間的值$D[l,r]$可以通過$d$來計算

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

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; }

?

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5919044.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。