交个暴力直接过,早知道就不写两只log做法了.(考试的时候想反正是个乱搞也没指望拿分就没写离散化,然鹅如果写了离散化就A了,,woc.)

思路:从上次的答案暴力往左/右移动位置直到最优.

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 2000020
int Q,an,bn,p[N],x[N],y[N],aa[N],bb[N],g[N],opt[N],gu;
int main(){
	Q=read();
	for(int T=1;T<=Q;++T){
		opt[T]=read(),p[T]=read();
		if(opt[T]==1)x[T]=read(),y[T]=read(),g[++gu]=x[T];
	}
	sort(g+1,g+gu+1);
	gu=unique(g+1,g+gu+1)-g-1;
	for(int i=1;i<=Q;++i){
		x[i]=lower_bound(g+1,g+gu+1,x[i])-g;
	}
	for(register int T=1,pos=0,sa=0,sb=0;T<=Q;++T){
		if(opt[T]==1){
			if(p[T]==0){
				aa[x[T]]+=y[T];
				if(x[T]<=pos)sa+=y[T];
			}
			else{
				bb[x[T]]+=y[T];
				if(x[T]>=pos)sb+=y[T];
			}
		}
		else{
			int o=p[T];
			if(p[o]==0){
				aa[x[o]]-=y[o];
				if(x[o]<=pos)sa-=y[o];
			}
			else{
				bb[x[o]]-=y[o];
				if(x[o]>=pos)sb-=y[o];
			}
		}
		while(pos>1&&min(sa-aa[pos],sb+bb[pos-1])>=min(sa,sb)&&sa>sb){
			--pos,sa-=aa[pos+1],sb+=bb[pos];
		}
		while(pos<gu&&min(aa[pos+1]+sa,sb-bb[pos])>=min(sa,sb)){
			++pos,sa+=aa[pos],sb-=bb[pos-1];
		}
		if(!sa||!sb){
			printf("Peace\n");
			continue;
		}
		printf("%d %d\n",g[pos],min(sa,sb)<<1);
	}
	return 0;
}

你看,没有线段树没有树状数组,用到的都是入门数据结构照样能A,这就是CCF出的省选数据结构题.

有人来hack么?