速通大ds记

通过一些手段，可以将这题转化为CF280D

于是在过完样例后，一发入魂AC了，喜

#include<bits/stdc++.h>
using namespace std;
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
#define It set<int>::iterator
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
//#define lson tr[rt].ls
//#define rson tr[rt].rs
//#define ls1 tr[rt1].ls
//#define rs1 tr[rt1].rs
//#define ls2 tr[rt2].ls
//#define rs2 tr[rt2].rs
#define pb emplace_back
const int mod=998244353;
#define int long long
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=1LL*res*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return res;
}
int max(int x,int y,int z){
	return max(x,max(y,z));
}
int min(int x,int y,int z){
	return min(x,min(y,z));
}
int n,q,p[200005];
int sum,res[200005];
struct tree{
	int l,r,val,lz_tag;
	int lmax,lmax_id,rmax,rmax_id,maxx,max_l,max_r;
	int lmin,lmin_id,rmin,rmin_id,minn,min_l,min_r;
	tree(int _l=0,int _r=0,int _val=0,int _lz_tag=0,
		int _lmax=0,int _lmax_id=0,int _rmax=0,int _rmax_id=0,int _maxx=0,int _max_l=0,int _max_r=0,
		int _lmin=0,int _lmin_id=0,int _rmin=0,int _rmin_id=0,int _minn=0,int _min_l=0,int _min_r=0):
		l(_l),r(_r),val(_val),lz_tag(_lz_tag),
		lmax(_lmax),lmax_id(_lmax_id),rmax(_rmax),rmax_id(_rmax_id),maxx(_maxx),max_l(_max_l),max_r(_max_r),
		lmin(_lmin),lmin_id(_lmin_id),rmin(_rmin),rmin_id(_rmin_id),minn(_minn),min_l(_min_l),min_r(_min_r){}
}tr[800005];
tree rev(tree x){
	x.lz_tag^=1;x.val=-x.val;
	x.lmax=-x.lmax;x.lmin=-x.lmin;
	x.rmax=-x.rmax;x.rmin=-x.rmin;
	x.maxx=-x.maxx;x.minn=-x.minn;
	swap(x.lmax,x.lmin);
	swap(x.lmax_id,x.lmin_id);
	swap(x.rmax,x.rmin);
	swap(x.rmax_id,x.rmin_id);
	swap(x.maxx,x.minn);
	swap(x.max_l,x.min_l);swap(x.max_r,x.min_r);
	return x;
}
tree operator+(const tree &x,const tree &y){
	tree z;
	z.l=x.l;z.r=y.r;z.val=x.val+y.val;
	if(x.val+y.lmax>=x.lmax)z.lmax=x.val+y.lmax,z.lmax_id=y.lmax_id;
	else z.lmax=x.lmax,z.lmax_id=x.lmax_id;
	if(x.val+y.lmin<=x.lmin)z.lmin=x.val+y.lmin,z.lmin_id=y.lmin_id;
	else z.lmin=x.lmin,z.lmin_id=x.lmin_id;
	if(y.val+x.rmax>=y.rmax)z.rmax=y.val+x.rmax,z.rmax_id=x.rmax_id;
	else z.rmax=y.rmax,z.rmax_id=y.rmax_id;
	if(y.val+x.rmin<=y.rmin)z.rmin=y.val+x.rmin,z.rmin_id=x.rmin_id;
	else z.rmin=y.rmin,z.rmin_id=y.rmin_id;
	z.maxx=max(x.maxx,y.maxx,x.rmax+y.lmax);
	if(z.maxx==x.maxx)z.max_l=x.max_l,z.max_r=x.max_r;
	else if(z.maxx==y.maxx)z.max_l=y.max_l,z.max_r=y.max_r;
	else z.max_l=x.rmax_id,z.max_r=y.lmax_id;
	z.minn=min(x.minn,y.minn,x.rmin+y.lmin);
	if(z.minn==x.minn)z.min_l=x.min_l,z.min_r=x.min_r;
	else if(z.minn==y.minn)z.min_l=y.min_l,z.min_r=y.min_r;
	else z.min_l=x.rmin_id,z.min_r=y.lmin_id;
	return z;
}
void push_up(int rt){
	int tag=tr[rt].lz_tag;
	tr[rt]=tr[ls]+tr[rs];
	tr[rt].lz_tag=tag;
}
void push_down(int rt){
	if(tr[rt].lz_tag==0)return ;
	tr[rt].lz_tag^=1;
	tr[ls]=rev(tr[ls]);
	tr[rs]=rev(tr[rs]);
}
void build(int rt,int l,int r){
	tr[rt].l=l;tr[rt].r=r;
	if(l==r){
		tr[rt].val=p[l];
		tr[rt].lmax=tr[rt].lmin=tr[rt].rmax=tr[rt].rmin=tr[rt].maxx=tr[rt].minn=p[l];
		tr[rt].lmax_id=tr[rt].lmin_id=tr[rt].rmax_id=tr[rt].rmin_id=tr[rt].max_l=tr[rt].max_r=tr[rt].min_l=tr[rt].min_r=l;
		return ;
	}
	build(ls,l,mid);build(rs,mid+1,r);
	push_up(rt);
}
void update(int rt,int l,int r,int ql,int qr){
	if(ql<=l && qr>=r){
		tr[rt]=rev(tr[rt]);
		return ;
	}else if(ql>r || qr<l)return ;
	push_down(rt);
	update(ls,l,mid,ql,qr);
	update(rs,mid+1,r,ql,qr);
	push_up(rt);
}
void work(){
	build(1,1,n);
	res[0]=tr[1].lmax;
//	printf("(%lld %lld %lld)\n",1,tr[1].lmax_id,tr[1].lmax);
//	printf("*** %lld %lld %lld\n",tr[1].maxx,tr[1].max_l,tr[1].max_r);
//	printf("*** %lld %lld %lld\n",tr[1].minn,tr[1].min_l,tr[1].min_r);
	update(1,1,n,1,tr[1].lmax_id);
	for(int i=1;i<=n;i++){
		res[i]=res[i-1]+tr[1].maxx;
//		printf("(%lld %lld %lld)\n",tr[1].max_l,tr[1].max_r,tr[1].maxx);
		update(1,1,n,tr[1].max_l,tr[1].max_r);
	}
	for(int i=1;i<=n;i++)res[i]=max(res[i],res[i-1]);
}
signed main(){
	freopen("end0.in","r",stdin);
	freopen("end0.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int c;scanf("%lld%lld",&c,&p[i]);
		if(c==1)p[i]=-p[i],sum-=p[i];
	}
	work();
//	for(int i=1;i<=n;i++)printf("%lld ",res[i]);puts("");
	scanf("%lld",&q);
	for(int i=1;i<=q;i++){
		int k;scanf("%lld",&k);
		printf("%lld\n",res[k]+sum);
	}
    return 0;
}