Description

題目背景

熱烈慶祝北京師范大學附屬實驗中學成立100周年！

問題描述

校慶籌備組的老師們正在尋找合適的地方來舉辦校慶慶典。學生們的位置和可以舉辦慶典的位置在x軸的正半軸取值在[1,n]的整數位置上。老師們選擇的地點是會根據參加典禮的學生位置來決定的，具體來說：定義一個位置的距離和為該位置到所有參加學生的距離之和。如果一個位置的距離和最小，且它比所有和它距離和相等的位置的位置更靠左，則老師們會選擇這個位置。開始時，所有的位置都可以舉辦慶典。但很可惜的是，并不是所有的位置都能舉辦慶典，有些奇怪的事件會使[l,r]這段區間不能舉辦慶典，不過有時也會使[l,r]可以重新舉辦慶典（并不保證[l,r]之前的每個位置都不能舉辦慶典）。有時一些學生會因為某些原因不能參加慶典，有時一些學生會主動報名參加慶典。作為一名合格的老師，你需要求出每個事件發生后慶典應該選擇的位置，如果沒有合法位置，請輸出-1。

Input

第一行包含兩個整數n,q，表示坐標的范圍和發生事件的個數。
第二行包含n個整數，第i個整數ai表示在初始時刻每個位置上的學生數量。
接下來q行每行先有一個整數type。
若type=1，接下來有兩個整數x,k，表示在x位置增加k名學生。
若type=2，接下來有兩個整數x,k，表示在x位置減少k名學生，保證x位置一定存在至少k名學生。
若type=3，接下來有兩個整數l,r，表示在[l,r]這段區間可以重新舉辦慶典。
若type=4，接下來有兩個整數l,r，表示在[l,r]這段區間不再能舉辦慶典。

Output

輸出總共q行，第i行的數為第i個事件發生后的答案。

Sample Input

5 4
1 0 1 0 0
1 4 1
2 3 1
4 1 3
3 2 3

Sample Output

3
1
4
2

樣例說明

總共5個位置可以選擇
第1個事件發生，新增加一名學生在4號位置。
第2個事件發生以前，學生分別在1,3,4位置，可以證明，在3的位置距離和最小且它是最靠左的那一個。
第2個事件發生，減少一名在3位置的學生。
第3個事件發生以前，學生分別在1,4位置，可以證明，在1的位置距離和最小且它是最靠左的那一個。
第3個事件發生，1到3號位置不能舉辦慶典。
第4個事件發生以前，學生分別在1,4位置，且1到3號位置不能舉辦慶典，可以證明，在4的位置距離和最小且它是最靠左的那一個。
第4個事件發生，2到3號位置能重新舉辦慶典。
最后，學生分別在1,4位置，且1號位置不能舉辦慶典，可以證明，在2的位置距離和最小且它是最靠左的那一個。

Data Constraint

對于20%的數據滿足，n ≤ 200, q ≤ 200
對于50%的數據滿足，n ≤ 2000, q ≤ 2000
對于另30%的數據滿足，不存在type = 3和type = 4的操作。
對于100%的數據滿足，1 ≤ n ≤ 2 ? 10^5, 1 ≤ q ≤ 2 ? 10^5, 1 ≤ k ≤ 2 ? 10^5, 0 ≤ ai ≤ 2 ? 10^5。

Solution

• 首先我們要知道慶典肯定是在中位數處舉辦最好。

• 如果一個位置已經不能舉辦了，那么一定是在這個位置左右最近的能舉辦的兩個位置中其中一個。

• 題述的四種操作都可以用線段樹維護。

• 之后二分一個位置查詢這個點 x 是否為中位數（區間查詢兩邊人數）。

• 若單點查詢 x 發現能舉辦，則直接輸出。

• 若不能舉辦，就區間查找 x 兩邊最近的點：

• 具體就是區間中維護 l,r ，表示一個區間中能夠達到的最近的點。

• 再區間查詢 (1,x?1) 的 r 和 (x+1,n) 的 l 即可。

• 那么如何判斷這兩個點哪個更優呢？

• 在線段樹中維護 a[i] 和 a[i]?i ，那么前半部分答案即為：a[i]?x?a[i]?i

• 后半部分取相反數即可，這樣就能統計出一個點作為舉辦位置的答案。

• 這樣的時間復雜度就是大常數的 O(N?log?N) 。

Code

#include<cstdio> using namespace std; const int N=2e5+2; int n; long long a[N]; long long num; template<typename T>T Max(T x,T y) {return x>y?x:y; } template<typename T>T Min(T x,T y) {return x<y?x:y; } struct Stream {inline int read(){int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w;}inline void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}inline void writeln(int x){if(x<0) x=-x,putchar('-');write(x),putchar('\n');} }Std; struct Segment_Tree {struct data{int l,r,c;long long num,sum;bool bz;}f[N<<3];inline void update(int v){int ls=v<<1,rs=ls|1;f[v].num=f[ls].num+f[rs].num;f[v].sum=f[ls].sum+f[rs].sum;f[v].bz=f[ls].bz|f[rs].bz;if(f[ls].bz) f[v].l=f[ls].l; elseif(f[rs].bz) f[v].l=f[rs].l; else f[v].l=n+1;if(f[rs].bz) f[v].r=f[rs].r; elseif(f[ls].bz) f[v].r=f[ls].r; else f[v].r=-1;}inline void modify(int v,int l,int r){int ls=v<<1,rs=ls|1;if(f[v].c==1){f[v].c=0;f[ls].c=f[rs].c=1;f[ls].bz=f[rs].bz=true;f[ls].l=l,f[rs].r=r;int mid=(l+r)>>1;f[ls].r=mid,f[rs].l=mid+1;}elseif(f[v].c==2){f[v].c=0;f[ls].c=f[rs].c=2;f[ls].bz=f[rs].bz=false;f[ls].l=f[rs].l=n+1;f[ls].r=f[rs].r=-1;}}inline void make(int v,int l,int r){if(l==r){f[v].l=f[v].r=l;f[v].num=a[l];f[v].sum=a[l]*l;f[v].bz=true;return;}int mid=(l+r)>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);update(v);}inline void change_num(int v,int l,int r,int x,int y){if(l==r){f[v].num+=y;f[v].sum+=(long long)y*l;return;}modify(v,l,r);int mid=(l+r)>>1;if(x<=mid) change_num(v<<1,l,mid,x,y); else change_num(v<<1|1,mid+1,r,x,y);update(v);}inline void change_bz(int v,int l,int r,int x,int y,bool z){if(l==x && r==y){f[v].bz=z;if(z) f[v].c=1; else f[v].c=2;if(!z) f[v].l=n+1,f[v].r=-1; else f[v].l=l,f[v].r=r;return;}modify(v,l,r);int mid=(l+r)>>1;if(y<=mid) change_bz(v<<1,l,mid,x,y,z); elseif(x>mid) change_bz(v<<1|1,mid+1,r,x,y,z); else{change_bz(v<<1,l,mid,x,mid,z);change_bz(v<<1|1,mid+1,r,mid+1,y,z);}update(v);}inline long long find_num(int v,int l,int r,int x,int y){if(l>=x && r<=y) return f[v].num;int mid=(l+r)>>1;if(y<=mid) return find_num(v<<1,l,mid,x,y);if(x>mid) return find_num(v<<1|1,mid+1,r,x,y);return find_num(v<<1,l,mid,x,mid)+find_num(v<<1|1,mid+1,r,mid+1,y);}inline long long find_sum(int v,int l,int r,int x,int y){if(l>=x && r<=y) return f[v].sum;int mid=(l+r)>>1;if(y<=mid) return find_sum(v<<1,l,mid,x,y);if(x>mid) return find_sum(v<<1|1,mid+1,r,x,y);return find_sum(v<<1,l,mid,x,mid)+find_sum(v<<1|1,mid+1,r,mid+1,y);}inline bool find_bz(int v,int l,int r,int x){modify(v,l,r);if(l==r) return f[v].bz;int mid=(l+r)>>1;bool bz=x<=mid?find_bz(v<<1,l,mid,x):find_bz(v<<1|1,mid+1,r,x);update(v);return bz;}inline int findl(int v,int l,int r,int x,int y){modify(v,l,r);if(l>=x && r<=y){if(!f[v].bz) return -1;return f[v].r;}int mid=(l+r)>>1;if(y<=mid) return findl(v<<1,l,mid,x,y);if(x>mid) return findl(v<<1|1,mid+1,r,x,y);return Max<int>(findl(v<<1,l,mid,x,mid),findl(v<<1|1,mid+1,r,mid+1,y));}inline int findr(int v,int l,int r,int x,int y){modify(v,l,r);if(l>=x && r<=y){if(!f[v].bz) return n+1;return f[v].l;}int mid=(l+r)>>1;if(y<=mid) return findr(v<<1,l,mid,x,y);if(x>mid) return findr(v<<1|1,mid+1,r,x,y);return Min<int>(findr(v<<1,l,mid,x,mid),findr(v<<1|1,mid+1,r,mid+1,y));}inline long long calc(int x){long long y=0;if(x>1) y=find_num(1,1,n,1,x-1)*x-find_sum(1,1,n,1,x-1);if(x<n) y+=find_sum(1,1,n,x+1,n)-find_num(1,1,n,x+1,n)*x;return y;} }Tree; int main() {n=Std.read();int q=Std.read();for(int i=1;i<=n;i++) num+=a[i]=Std.read();Tree.make(1,1,n);while(q--){int type=Std.read(),x=Std.read(),y=Std.read();if(type==1) Tree.change_num(1,1,n,x,y),num+=y;if(type==2) Tree.change_num(1,1,n,x,-y),num-=y;if(type==3) Tree.change_bz(1,1,n,x,y,true);if(type==4) Tree.change_bz(1,1,n,x,y,false);int l=1,r=n,ans=0;long long sl=0,sr=0,midnum=(num+1)>>1;while(l<=r){int mid=(l+r)>>1;long long z=Tree.find_num(1,1,n,l,mid);if(sl+z<midnum) ans=mid,l=mid+1,sl+=z; else r=mid-1,sr+=num-sr-sl-z;}if(Tree.find_bz(1,1,n,++ans)){Std.writeln(ans);continue;}int ans1=ans>1?Tree.findl(1,1,n,1,ans-1):-1;int ans2=ans<n?Tree.findr(1,1,n,ans+1,n):n+1;if((ans1<0 || ans1>n) && (ans2<0 || ans2>n)){Std.writeln(-1);continue;}int node=ans1;if((ans1<0 || ans1>n) || ans2>0 && ans2<=n && Tree.calc(ans1)>Tree.calc(ans2)) node=ans2;Std.writeln(node);}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5419. 【NOIP2017提高A组集训10.24】筹备计划的全部內容，希望文章能夠幫你解決所遇到的問題。

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