自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:15:38，当前版本为作者最后更新于2025-05-09 21:50:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Solution

简单数据结构题。考虑上一些小套路。

将第一问的和式改为：

$$\sum_{t \ge 1} \sum_{i=1}^{n-k+1} [(\max_{i \le p \le i+k-1} a_p) \ge t] $$

考虑稍微转化一下，设 $a$ 的上界为 $V$，改为：

$$(n-k+1)V - \sum_{t = 1}^V \sum_{i=1}^{n-k+1} [(\min_{i \le p \le i+k-1} a_p) < t] $$

这个怎么看呢，考虑记 $b_i = [a_i \ge t]$，$b$ 中相邻两个 $1$ 的距离分别为 $len_{1,2,\cdots,z}$（特别的认为 $b_0=b_{n+1}=1$），那么 $t$ 固定的时候和式就是 $\sum_{i=1}^z \max\{0,len_i - k + 1\}$。你把 $len$ 扔进一个树状数组中，就可以快速求解。

由于只有 $a_k \leftarrow a_k+1$ 的操作，所以每次只会有 $O(1)$ 个 $len$ 发生改变，直接暴力修改。

有一个小问题，你怎么处理初始的 $len$。有用的观察：存在 $t$ 使得 $b_i = b_j = 1$，$b_{i+1} = b_{i+2} = \cdots = b_{j-1} = 0$ 的 $(i,j)$ 只有 $O(n)$ 对。具体怎么做可以参考 JOISC 的铁道旅行（其实就是一个简单的单调栈）。

复杂度 $O(n \log n)$，足以通过本题。

非常罕见的不是特别慢。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,q,a[MAXN],t[MAXN<<2],V=2e9;
int tr[MAXN][2];
void Update(int pos,int v1,int v2) {
	pos=n-pos+1;
	while(pos<=n) tr[pos][0]+=v1,tr[pos][1]+=v2,pos+=pos&-pos;
	return ;
}
pair<int,int> Query(int pos) {
	int ans1=0,ans2=0;
	pos=n-pos+1;
	while(pos) ans1+=tr[pos][0],ans2+=tr[pos][1],pos-=pos&-pos;
	return {ans1,ans2};	
}
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
void build(int k,int l,int r) {
	if(l==r) return t[k]=a[l],void();
	build(lson,l,mid),build(rson,mid+1,r);
	return t[k]=max(t[lson],t[rson]),void();	
}
int query(int k,int l,int r,int x,int y) {
	if(x<=l&&r<=y) return t[k];
	if(y<=mid) return query(lson,l,mid,x,y);
	if(x>mid) return query(rson,mid+1,r,x,y);
	return max(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y));	
}
void modify(int k,int l,int r,int pos,int v) {
	if(l==r) return t[k]=v,void();
	if(pos<=mid) modify(lson,l,mid,pos,v);
	else modify(rson,mid+1,r,pos,v);
	return t[k]=max(t[lson],t[rson]),void();	
}
int bfind1(int k,int l,int r,int pos,int v) {
	if(r<pos||t[k]<v) return -1;
	if(l==r) return l;
	int tans=bfind1(lson,l,mid,pos,v);
	if(tans!=-1) return tans;
	return bfind1(rson,mid+1,r,pos,v);	
}
int bfind2(int k,int l,int r,int pos,int v) {
	if(l>pos||t[k]<v) return -1;
	if(l==r) return l;
	int tans=bfind2(rson,mid+1,r,pos,v);
	if(tans!=-1) return tans;
	return bfind2(lson,l,mid,pos,v);
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	ffor(i,1,n) cin>>a[i];
	a[0]=a[n+1]=V,build(1,0,n+1);
	stack<int> st; st.push(0);
	ffor(i,1,n+1) {
		while(!st.empty()&&a[i]>=a[st.top()]) {
			int l=st.top()+1,r=i-1;
			st.pop();
			if(l<=r) Update(r-l+1,min(a[l-1],a[r+1])-query(1,0,n+1,l,r),(r-l+1)*(min(a[l-1],a[r+1])-query(1,0,n+1,l,r)));
		}
		if(!st.empty()) {
			int l=st.top()+1,r=i-1;	
			if(l<=r) Update(r-l+1,min(a[l-1],a[r+1])-query(1,0,n+1,l,r),(r-l+1)*(min(a[l-1],a[r+1])-query(1,0,n+1,l,r)));
		}
		st.push(i);
	}
	ffor(i,1,q) {
		char op;
		int k;
		cin>>op>>k;
		if(op=='?') {
			auto pr=Query(k);
			cout<<V*(n-k+1)-(pr.second-(k-1)*pr.first)<<'\n';
		}
		else {
			int L=bfind2(1,0,n+1,k,a[k]+1)+1,R=bfind1(1,0,n+1,k,a[k]+1)-1;
			Update(R-L+1,-1,-(R-L+1));
			if(L<=k-1) Update(k-L,1,k-L);
			if(k+1<=R) Update(R-k,1,R-k);
			a[k]++,modify(1,0,n+1,k,a[k]);
		}
	}
	return 0;
}