C++14(g++5.4) 解法, 执行用时: 111ms, 内存消耗: 4300K, 提交时间: 2018-12-22 14:00:00

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
typedef long long ll;
int n,m,i;
int op[N],x[N],y[N],z[N];
int qid[N];
int ans[N];
ll bi1[N],bi2[N];
inline void add(ll*a,int x,int v){for(;x<=n;x+=x&-x)a[x]+=v;}
inline ll query(ll*a,int x){ll ans=0;for(;x;x-=x&-x)ans+=a[x];return ans;}
inline void add(int l,int r,int v){
	add(bi1,l,v);add(bi1,r+1,-v);
	add(bi2,l,v*(l-1));add(bi2,r+1,-r*v);
}
inline ll sum(int x){return 1ll*query(bi1,x)*x-query(bi2,x);}
inline ll sum(int l,int r){return sum(r)-sum(l-1);}
void solve(int a,int b,int c,int d){
	if(a>b)return;
	if(c==d){
		for(int i=a;i<=b;++i)if(op[qid[i]]==2)ans[qid[i]]=c;
		return;
	}
	int mid=(c+d)>>1,i;
	static ll ff[N];
	memset(ff+a,0,(b-a+1)<<3);
	//{std::cerr<<sum(26890,30000)<<'\n';exit(0);}
	for(i=a;i<=b;++i){
		if(op[qid[i]]==1 && z[qid[i]]<=mid){
			add(x[qid[i]],y[qid[i]],1);
		}
	//if(i==2){std::cerr<<sum(30000)<<'\n';exit(0);}
		if(op[qid[i]]==2)ff[i]+=sum(x[qid[i]],y[qid[i]]);
	}
	//std::cerr<<sum( 26890,30428)<<'\n';exit(0);
	static int ql[N],qr[N];int lxb=0,rxb=0;
	for(i=a;i<=b;++i){
		if(op[qid[i]]==1 && z[qid[i]]<=mid){
			add(x[qid[i]],y[qid[i]],-1);
		}
	}
	for(i=a;i<=b;++i){
		if(op[qid[i]]==1){
			if(z[qid[i]]<=mid)ql[++lxb]=qid[i];else qr[++rxb]=qid[i];
		}else{
			if(ff[i]>=z[qid[i]])ql[++lxb]=qid[i];else qr[++rxb]=qid[i],z[qid[i]]-=ff[i];
		}
	}
	for(i=1;i<=lxb;++i)qid[a-1+i]=ql[i];
	for(i=1;i<=rxb;++i)qid[a+lxb-1+i]=qr[i];
	solve(a,a+lxb-1,c,mid);solve(a+lxb,b,mid+1,d);
}
int main(){
	//freopen("1.txt","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	for(i=1;i<=m;++i){
		cin>>op[i]>>x[i]>>y[i]>>z[i],qid[i]=i;
		if(op[i]==1)z[i]=-z[i];
	}
	solve(1,m,-n-1,n+1);
	for(i=1;i<=m;++i)if(op[i]==2)cout<<-ans[i]<<'\n';
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 688ms, 内存消耗: 64864K, 提交时间: 2019-01-07 18:24:48

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,now,rt,cnt=0,root[200005],tag[15000005],lc[15000005],rc[15000005];
unsigned int sumv[15000005];
int Hash[50005];
struct operation{
 int op,a,b,c;
}a[50005];
int getid(int a){
 return lower_bound(Hash+1,Hash+Hash[0]+1,a)-Hash;
}
void upd(int &o,int l,int r,int L,int R){
 if(!o) o=++cnt;
 sumv[o]+=R-L+1;
 if(L==l&&R==r)
 {
  tag[o]++;
  return;
 }
 int mid=(l+r)/2;
 if(R<=mid) upd(lc[o],l,mid,L,R);
 else if(L>mid) upd(rc[o],mid+1,r,L,R);
 else
 {
  upd(lc[o],l,mid,L,mid);
  upd(rc[o],mid+1,r,mid+1,R);
 }
}
void update(int o,int l,int r,int k){
 upd(root[o],1,n,a[now].a,a[now].b);
 if(l==r) return;
 int mid=(l+r)/2;
 if(k<=mid) update(o*2,l,mid,k);
 else update(o*2+1,mid+1,r,k);
}
unsigned int qry(int o,int l,int r,int L,int R){
 if(!o) return 0;
 if(L==l&&R==r) return sumv[o];
 int mid=(l+r)/2;
 unsigned int ans=tag[o]*(R-L+1);
 if(R<=mid) ans+=qry(lc[o],l,mid,L,R);
 else if(L>mid) ans+=qry(rc[o],mid+1,r,L,R);
 else ans+=qry(lc[o],l,mid,L,mid)+qry(rc[o],mid+1,r,mid+1,R);
 return ans;
}
int query(int o,int l,int r,int k){
 if(l==r) return l;
 int mid=(l+r)/2;
 unsigned int siz=qry(root[o*2+1],1,n,a[now].a,a[now].b);
 if(k>siz) return query(o*2,l,mid,k-siz);
 else return query(o*2+1,mid+1,r,k);
}
int main(){
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++){
  scanf("%d%d%d%d",&a[i].op,&a[i].a,&a[i].b,&a[i].c);
  if(a[i].op==1) Hash[++Hash[0]]=a[i].c;
 }
 sort(Hash+1,Hash+Hash[0]+1);
 Hash[0]=unique(Hash+1,Hash+Hash[0]+1)-Hash-1;
 for(int i=1;i<=m;i++){
  now=i;
  if(a[i].op==1) update(1,1,50000,getid(a[i].c));
  else printf("%d\n",Hash[query(1,1,50000,a[i].c)]);
 }
 return 0;
}