自动搬运

查看原文

来自洛谷，原作者为

	zifanwang RP++

搬运于2025-08-24 22:07:11，当前版本为作者最后更新于2023-08-11 12:53:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提高 T1 难度 远古 JOI 题。这东西能评黑？？？

• 题目链接

干什么

有两个长度为 $n$ 个序列 $(x_1,x_2,\dots,x_n),(y_1,y_2,\dots,y_n)$，初始化 $x_i=y_i=i$。有 $q$ 次操作，每次给你三个数 $X,D,L$，若 $D=1$ 将所有满足 $x_i\le X$ 的 $i$ 的 $y_i$ 减 $2L$，若 $D=2$ 则将所有满足 $y_i> X$ 的 $i$ 的 $x_i$ 加 $2L$，求出最终的 $x,y$ 序列。

怎么做

发现 $x,y$ 两个序列任意时刻都是单调递增的，两种操作分别是前缀减和后缀加，二分出修改的区间然后树状数组维护即可，时间复杂度 $O(q\log^2 n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 200003
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
struct node{
	ll x,d,l;
}a[mxn];
int n,q;
struct tree{
	ll c[mxn];
	void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
	ll ask(int x){
		ll s=0;
		for(;x;x-=x&-x)s+=c[x];
		return s;
	}
}c1,c2;
signed main(){
	scanf("%d%d",&n,&q);
	rep(i,1,q)scanf("%lld%lld%lld",&a[i].x,&a[i].d,&a[i].l),a[i].l<<=1;
	rep(i,1,n)c1.add(i,1),c2.add(i,1);
	drep(j,q,1){
		if(a[j].d==1){
			int l=1,r=n;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(c1.ask(mid)<=a[j].x)l=mid;
				else r=mid-1;
			}
			if(c1.ask(l)<=a[j].x)c2.add(1,-a[j].l),c2.add(l+1,a[j].l);
		}else{
			int l=1,r=n;
			while(l<r){
				int mid=(l+r)>>1;
				if(c2.ask(mid)>a[j].x)r=mid;
				else l=mid+1;
			}
			if(c2.ask(l)>a[j].x)c1.add(l,a[j].l);
		}
	}
	rep(i,1,n)printf("%lld\n",(c1.ask(i)-c2.ask(i))>>1);
	return 0;
}