130分WA,线段树update和query求条
查看原帖
130分WA,线段树update和query求条
642173
KarmaticEnding楼主2024/10/2 22:04

这道题我已经把问题锁定在了循环while(q--)当中,但是死活就是没看出哪里有问题

评测结果:第一个样例没过,最后一行输出 9-9

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
#define ls rt<<1
#define rs (rt<<1)|1
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
int n,q;
long long ans=0;
long long val[MAXN<<2];
long long tot[MAXN<<2];
inline void pushup(int rt){
	val[rt]=val[ls]+val[rs];
	tot[rt]=tot[ls]+tot[rs];
}
void update(int pos,int valu,int cnt,int l,int r,int rt){
	if(l==r){
		val[rt]+=valu;
		tot[rt]+=cnt;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		update(pos,valu,cnt,lson);
	}
	else{
		update(pos,valu,cnt,rson);
	}
	pushup(rt);//每日忘写pushup(1/1)
}
long long query(int L,int R,int l,int r,int rt,bool flg){
	if(L<=l&&r<=R){
		if(flg){
			return tot[rt];
		}
		else{
			return val[rt];
		}
	}
	int mid=(l+r)>>1;
	long long res=0;
	if(L<=mid){
		res+=query(L,R,lson,flg);
	}
	if(R>mid){
		res+=query(L,R,rson,flg);
	}
	return res;
}
struct CUSTOM{
	int l_cometime;
	int t_maketime;
	int id;
	bool operator<(const CUSTOM &rhs)const{
		return t_maketime<rhs.t_maketime;
	}
}c[MAXN];
int newpos[MAXN];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&c[i].l_cometime,&c[i].t_maketime);
		c[i].id=i;
	}
	sort(c+1,c+n+1);
	for(int i=1;i<=n;++i){
		ans=ans+((long long)(c[i].l_cometime)-(long long)(n-i+1)*c[i].t_maketime);
	}
	printf("%lld\n",ans);
	for(int i=1;i<=n;++i){
		update(c[i].t_maketime,c[i].t_maketime,1,1,n,1);
		newpos[c[i].id]=i;
	}
	while(q--){
		int k,ll,tt;
		scanf("%d%d%d",&k,&ll,&tt);
		update(c[newpos[k]].t_maketime,-c[newpos[k]].t_maketime,-1,1,n,1);
		long long a=query(1,c[newpos[k]].t_maketime,1,n,1,false),b=query(1,c[newpos[k]].t_maketime,1,n,1,true);//b->前面还有多少数 a->前面数的和
		ans-=c[newpos[k]].l_cometime;
		ans+=(n-b)*(c[newpos[k]].t_maketime);
		ans+=a;
		c[newpos[k]].t_maketime=tt;
		c[newpos[k]].l_cometime=ll;
		ans+=c[newpos[k]].l_cometime;
		a=query(1,c[newpos[k]].t_maketime,1,n,1,false),b=query(1,c[newpos[k]].t_maketime,1,n,1,true);
		ans-=(n-b)*(c[newpos[k]].t_maketime);
		ans-=a;
		update(c[newpos[k]].t_maketime,c[newpos[k]].t_maketime,1,1,n,1);
		printf("%lld\n",ans);
	}
	return 0;
}

2024/10/2 22:04
加载中...