题目背景
热烈庆祝北京师范大学附属实验中学成立100周年！
问题描述
校庆筹备组的老师们正在寻找合适的地方来举办校庆庆典。
学生们的位置和可以举办庆典的位置在x轴的正半轴取值在[1,n]的整数位置上。
老师们选择的地点是会根据参加典礼的学生位置来决定的，具体来说：定义一个位置的距离和为该位置到所有参加学生的距离之和。如果一个位置的距离和最小，且它比所有和它距离和相等的位置的位置更靠左，则老师们会选择这个位置。
开始时，所有的位置都可以举办庆典。但很可惜的是，并不是所有的位置都能举办庆典，有些奇怪的事件会使[l,r]这段区间不能举办庆典，不过有时也会使[l,r]可以重新举办庆典（并不保证[l,r]之前的每个位置都不能举办庆典）。
有时一些学生会因为某些原因不能参加庆典，有时一些学生会主动报名参加庆典。
作为一名合格的老师，你需要求出每个事件发生后庆典应该选择的位置，如果没有合法位置，请输出-1。
数据结构什么的最无脑了2333
贪心，首先先来说没有奇怪事件的情况
很明显就是一个带权中位数了，可以用一个树状数组+二分搞定
那么加上了奇怪事件，那么显然，如果最优位置被覆盖后，显然选择的位置离最有位置越近越优，所以用一个线段树区间覆盖，让后二分找出离最优点最近的两个取较优即可
代码长度碾压所有其他选手，然而时间几乎垫底
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
#define N 200010
#define mid (l+r>>1)
using namespace std;
int n,m; bool vis[N]; LL S=0;
struct Seg{
LL s[N],c[N],v;
LL cum(int x){ for(v=0;x;x^=x&-x) v+=c[x]; return v; }
LL sum(int x){ for(v=0;x;x^=x&-x) v+=s[x]; return v; }
void add(int x,LL k){ for(v=k*x;x<=n;x+=x&-x) s[x]+=v,c[x]+=k; }
LL gC(int l,int r){ return cum(r)-cum(l-1); }
LL gS(int l,int r){ return sum(r)-sum(l-1); }
} s;
int w[N<<2],t[N<<2];
inline void pd(int x,int m){
if(t[x]){
t[x<<1]=t[x];
t[x<<1|1]=t[x]; --t[x];
w[x<<1]=t[x];
w[x<<1|1]=t[x];
t[x]=0;
}
}
void build(int l,int r,int x){
if(l==r){ w[x]=1; t[x]=0; return; }
build(l,mid,x<<1); build(mid+1,r,x<<1|1);
w[x]=w[x<<1]|w[x<<1|1];
}
void update(int l,int r,int x,int L,int R,int k){
if(L<=l && r<=R){ w[x]=k; t[x]=k+1; return; }
pd(x,r-l+1);
if(L<=mid) update(l,mid,x<<1,L,R,k);
if(mid<R) update(mid+1,r,x<<1|1,L,R,k);
w[x]=w[x<<1]|w[x<<1|1];
}
int query(int l,int r,int x,int L,int R){
if(L<=l && r<=R) return w[x];
pd(x,r-l+1); int ans=0;
if(L<=mid) ans|=query(l,mid,x<<1,L,R);
if(mid<R) ans|=query(mid+1,r,x<<1|1,L,R);
return ans;
}
LL cal(int j){
if(j<1 || j>n) return 1ll<<60;
LL c,A;
c=s.gC(1,j-1); A=c*j-s.gS(1,j-1);
c=s.gC(j+1,n); A+=s.gS(j+1,n)-j*c;
return A;
}
int prt2(){
freopen("position.in","r",stdin);
freopen("position.out","w",stdout);
scanf("%d%d",&n,&m);
for(int x,i=1;i<=n;++i){
scanf("%d",&x);
s.add(i,x); S+=x;
} build(1,n,1);
for(int o,l,r,p,M;m--;){
scanf("%d%d%d",&o,&l,&r);
if(o==1){ s.add(l,r); S+=r; }
else if(o==2){ s.add(l,-r); S-=r; }
else if(o==3) update(1,n,1,l,r,1);
else update(1,n,1,l,r,0);
l=1,r=n;
for(;l<r;){
M=l+r>>1;
if((s.gC(1,M)<<1)<S) l=M+1;
else r=M;
}
p=l;
if(query(1,n,1,p,p)) printf("%d
",p);
else {
for(l=0,r=p-1;l<r;){
M=l+r+1>>1;
if(query(1,n,1,M,p)) l=M;
else r=M-1;
}
o=l;
for(l=p+1,r=n+1;l<r;){
M=l+r>>1;
if(query(1,n,1,p,M)) r=M;
else l=M+1;
}
if(o==0 && l==n+1) puts("-1");
else printf("%d
",cal(o)>cal(l)?l:o);
}
}
}
int main(){ prt2(); }