自动搬运

查看原文

来自洛谷，原作者为

	meyi 明日黄花

搬运于2025-08-24 22:31:27，当前版本为作者最后更新于2021-07-12 17:54:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

2021/9/30 UPD: 感谢 $\text{\color{black}{s}\color{red}{yksykCCC}}$ 指出本题解中的一处错误。

提供一个从dmy老师那里嫖来的单 $\log$ 做法，截至本题解发布时为最优解。

我们在写有区间操作的数据结构题时，一般以时间（即操作的先后顺序）为第一维，维护以横坐标为第二维的相关数据。在允许离线的题目上，有这样一种常用做法：以横坐标为第一维，维护以时间为第二维的相关数据。

回到本题，我们维护一个树状数组，若第 $i$ 个操作为修改操作，则在 $l_i$ 处记录“在树状数组的第 $i$ 个位置加上 $x_i$”，在 $r_i+1$ 处记录“在树状数组的第 $i$ 个位置减去 $x_i$”。然后我们从 $1$ 到 $n$ 枚举横坐标，对于每个询问，先将当前处时间小于它的操作加到树状数组中，然后查询树状数组中第一个前缀和 $\ge \lceil\frac{sum}{2}\rceil$ 的下标即可，其中 $sum$ 表示当前的总和。可以通过树状数组上二分的黑科技做到单 $\log$。

（顺带一提 IOI2021D1T1 也用到了类似套路

实现细节可以看代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5+10;
#define lowbit(k) ((k)&(-k))
template<typename T>
struct BIT{
	T c[maxn];
	int mx_idx;
	inline void clear(){memset(c,0,sizeof(T)*(mx_idx+1));}
	inline void add(int k,T v){
		for(;k<=mx_idx;k+=lowbit(k))c[k]+=v;
	}
	inline T query(int k){
		T ret=0;
		for(;k;k^=lowbit(k))ret+=c[k];
		return ret;
	}
	inline T query(int l,int r){
		return query(r)-query(l-1);
	}
	inline int half(ll k){
		if(!k)return 0;
		ri now=0;
		ll tot=0;
		for(ri i=1<<16;i;i>>=1){
			ri nxt=now|i;
			if(nxt<=mx_idx&&tot+c[nxt]<k)now=nxt,tot+=c[nxt];
		}
		return now+1;
	}
};
BIT<ll>c;
int ans[maxn],cnt,m,n;
struct node{
	bool tp;
	int pos,val;
};
vector<node>q[maxn];
#define pb push_back
int main(){
	scanf("%d%d",&n,&m);
	c.mx_idx=m;
	for(ri i=1;i<=m;++i){
		ri op,x,y,z;
		scanf("%d%d",&op,&x);
		if(op)q[x].pb({op,i,++cnt});
		else{
			scanf("%d%d",&y,&z);
			q[x].pb({op,i,z});
			q[y+1].pb({op,i,-z});
		}
	}
	for(ri i=1;i<=n;++i)
		for(node j:q[i])
			if(j.tp){
				ans[j.val]=j.pos-c.half((c.query(j.pos)+1)>>1);
			}
			else{
				c.add(j.pos,j.val);
			}
	for(ri i=1;i<=cnt;++i)printf("%d\n",ans[i]);
	return 0;
}