自动搬运

查看原文

来自洛谷，原作者为

	wangshulin 原来我不是菜，我是铸币

搬运于2025-08-24 23:10:04，当前版本为作者最后更新于2024-12-14 17:34:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

暴力

• 合法区间的右端点是连续的，暴力树状数组递推求逆序对即可。

• 特殊性质 A：

  若存在合法区间，区间左端点固定为 $l_{k}$，区间右端点必定是 $[l_{k},n]$ 种任意一个数，所以从后往前递推树状数组求每种可能的 $l_{k}$ 对应的答案即可。

后面所有讲解都要用的前置性质

设右端点的取值范围为 $[L,R]$，显然 $c_{L}=1$，$\forall i \in [L+1,R],c_{i}=0$，又显然 $[L,R]$ 的取值最多只有 $n$ 种，因为整个 $[1,n]$ 的区间是由若干个不重合的 $[L,R]$ 区间拼成的，所以我们将询问按其对应的 $[L,R]$ 分类。

设 $f(l,r)$ 为区间 $[l,r]$ 的逆序对个数，贡献可以分为了三部分：

• 左部分区间：$f(l,L-1)$。
• 右部分区间：$\sum_{i=L}^{R} f(L,i)$。
• 两区间之间：$\sum_{i=L}^{R} \sum_{j=l}^{L-1} \sum_{k=L}^{i}[a_{j}>a_{k}]$。

两区间之间的贡献的求法

• 对序列进行分块，对于每一个块用树状数组预处理其和每个区间 $[L,R]$ 之间的贡献，是 $O(n \sqrt n \log n)$ 的，查询时先遍历整块求所有整块的贡献和，剩下残块的贡献用类似的方法用树状数组求，是 $O(n \sqrt n \log n)$ 的。

• 特殊性质 C：

  每个区间 $[L,R]$ 的长度都为 $1$，所以直接比较，不需要树状数组维护。

• 发现如上算法中，一共有 $O(n)$ 次加入，和 $O(n \sqrt n)$ 次查询，这显然可以用根号平衡——使用 $O(\sqrt n)$ 加入，$O(1)$ 查询的分块数据结构即可。

左区间贡献的求法

• 特殊性质 B：

  左区间的 $c_{i}$ 是全 $0$ 段，且右端点为 $n$ 或右边一位的 $c_{i}$ 为 $1$，性质和右区间的出现相似，所以可以参考下文右区间贡献的求法。

• 左区间是固定区间，相当于求区间逆序对，可以用莫队暴力 $O(n\sqrt m \log n)$ 做，可跑过 $n \le 5 \times 10^{4}$ 的点。

• 特殊性质 D：

  这个特殊性质下的左区间的左端点和右端点都是递增的，意味着不需要做 $O(n \sqrt m)$ 次莫队更新，只需要 $O(m)$ 递推，时间复杂度降到 $O(n \log n)$。

• $O(n \sqrt m)$ 的正解做法参考 P5047。

右区间贡献的求法

• 特殊性质 C:

  右区间长度为 $1$，不需要处理其贡献。

• 所有右区间拥有共同的左端点，参考性质 A 的方法。

最终时间复杂度即优化为 $O(n\sqrt m+n\sqrt n)$。

上述题解中存在两种贡献的求解需要从带 $\log$ 优化到不带 $\log$，但是根据测试数据的强度看选手只需要会其中一个就足以通过了（我们又不是 Ynoi，真的卡不掉啊！）

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200010,B=500,CB=(N+B-1)/B;
int n,m,cq,clis,a[N],c[N],sc[N],lis[N],bel[N],lef[CB],rig[CB];
ll g[N],ans[N],fl[N],fr[N],sfl[N],sfr[N],Id[N<<2],cnt[CB][N];
vector<int> gId[N];
vector<ll> ansl[N],ansr[N];
vector<pair<int,int>> gl[N],gr[N];
int qbel(int x){
	return (x+B-1)/B;
}
int qlef(int x){
	return max(0,B*(x-1)+1);
}
int qrig(int x){
	return min(n,B*x);
}
namespace DS{
	struct BIT{
		ll t[N];
		void clear(){
			memset(t,0,sizeof(t));
		}
		int lowbit(int x){
			return x&-x;
		}
		void add(int k,ll x){
			for(int i=k;i<=n;i+=lowbit(i)) t[i]+=x;
		}
		ll query(int k){
			ll s=0;
			for(int i=k;i;i-=lowbit(i)) s+=t[i];
			return s;
		}
		ll query(int l,int r){
			if(l>r) return 0;
			else return query(r)-query(l-1);
		}
	}tr;
	struct BLC{
		ll val[N],tag[CB];
		void clear(){
			memset(val,0,sizeof(val));
			memset(tag,0,sizeof(tag));
		}
		void add(int k,ll x){//单点加——O(\sqrt n)
			for(int i=k;i<=rig[bel[k]];i++) val[i]+=x;
			for(int i=bel[k]+1;i<=bel[n];i++) tag[i]+=x;
		}
		ll query(int l){//前缀查询——O(1)
			return val[l]+tag[bel[l]];
		}
		ll query(int l,int r){
			if(l>r) return 0;
			else return query(r)-query(l-1);
		}
	}blc;
};
struct query{
	int x,d,l,r;
}p[N];
struct MO_query{
	int l,r,Id;
	bool operator<(const MO_query &o)const{
		if(bel[l]!=bel[o.l]) return bel[l]<bel[o.l];
		else{
			if(bel[l]&1) return r<o.r;
			else return r>o.r;
		}
	}
}q[N];
void PART_1(){
	DS::tr.clear();
	DS::blc.clear();
	int L,R,cnt;
	ll res;
	sort(q+1,q+cq+1);
	L=1,R=0,cnt=0;
	for(int i=1;i<=cq;i++){
		if(R<q[i].r) gr[L-1].push_back({R+1,q[i].r}),ansr[L-1].push_back(0),Id[++cnt]=ansr[L-1].size()-1,R=q[i].r;
		if(L>q[i].l) gl[R].push_back({q[i].l,L-1}),ansl[R].push_back(0),Id[++cnt]=ansl[R].size()-1,L=q[i].l;
		if(R>q[i].r) gr[L-1].push_back({q[i].r+1,R}),ansr[L-1].push_back(0),Id[++cnt]=ansr[L-1].size()-1,R=q[i].r;
		if(L<q[i].l) gl[R].push_back({L,q[i].l-1}),ansl[R].push_back(0),Id[++cnt]=ansl[R].size()-1,L=q[i].l;
	}
	for(int i=0;i<=n;i++){
		if(i){
			fr[i]=DS::blc.query(a[i]+1,n);
			DS::blc.add(a[i],1);
			fl[i]=DS::blc.query(a[i]-1);
			sfl[i]=sfl[i-1]+fl[i];
			sfr[i]=sfr[i-1]+fr[i];
		}
		for(int j=0;j<gl[i].size();j++){
			for(int k=gl[i][j].first;k<=gl[i][j].second;k++) ansl[i][j]+=DS::blc.query(a[k]-1);
		}
		for(int j=0;j<gr[i].size();j++){
			for(int k=gr[i][j].first;k<=gr[i][j].second;k++) ansr[i][j]+=DS::blc.query(a[k]+1,n);
		}
	}
	L=1,R=0,cnt=0,res=0;
	for(int i=1;i<=cq;i++){
		if(R<q[i].r) res+=(sfr[q[i].r]-sfr[R])-ansr[L-1][Id[++cnt]],R=q[i].r;
		if(L>q[i].l) res+=ansl[R][Id[++cnt]]-(sfl[L-1]-sfl[q[i].l-1]),L=q[i].l;
		if(R>q[i].r) res-=(sfr[R]-sfr[q[i].r])-ansr[L-1][Id[++cnt]],R=q[i].r;
		if(L<q[i].l) res-=ansl[R][Id[++cnt]]-(sfl[q[i].l-1]-sfl[L-1]),L=q[i].l;
		ans[q[i].Id]+=res*(p[q[i].Id].r-p[q[i].Id].l+1);
	}
}
void PART_2(){
	DS::tr.clear();
	DS::blc.clear();
	for(int l=1,r;l<=n;l=r+1){//预处理计算块完整/不完整时的贡献——O(n\log n)
		for(r=l;r<=n&&sc[r]==sc[l];r++) ;
		r--;
		ll t=0;
		for(int j=r;j>=l;j--){
			t+=DS::tr.query(a[j]-1);
			DS::tr.add(a[j],r-j+1);
		}
		g[l]=t;
		for(int j=l;j<=r;j++){//从 l 到 r 删除
			t-=DS::tr.query(a[j]-1);//去除 a_{j} 往后贡献的逆序对
			if(j<r) g[j+1]=t;
			DS::tr.add(a[j],-(r-j+1));
		}
	}
	for(int i=1;i<=bel[n];i++){//开始计算 [1,l-1] 和 [l,r] 之间的贡
		for(int j=lef[i];j<=rig[i];j++) DS::blc.add(a[j],1);
		for(int l=1,r;l<=n;l=r+1){
			for(r=l;r<=n&&sc[r]==sc[l];r++) ;
			r--;
			if(rig[i]>=l) continue;
			for(int j=l;j<=r;j++) cnt[i][l]+=DS::blc.query(a[j]+1,n)*(r-j+1);
		}
		for(int j=lef[i];j<=rig[i];j++) DS::blc.add(a[j],-1);
	}
	for(int l=1,r;l<=n;l=r+1){//开始计算 [1,l-1] 和 [l,r] 之间的贡献
		for(r=l;r<=n&&sc[r]==sc[l];r++) ;
		r--;
		for(int i=l;i<=r;i++) DS::blc.add(a[i],r-i+1);
		for(auto i:gId[l]){
			if(p[i].x>=p[i].l){
				ans[i]=g[p[i].x];
				continue;
			}
			ans[i]+=g[p[i].l];
			if(bel[p[i].x]==bel[p[i].l-1]){
				for(int j=p[i].x;j<=p[i].l-1;j++) ans[i]+=DS::blc.query(a[j]-1);
			}else{
				for(int j=p[i].x;j<=rig[bel[p[i].x]];j++) ans[i]+=DS::blc.query(a[j]-1);
				for(int j=bel[p[i].x]+1;j<bel[p[i].l-1];j++) ans[i]+=cnt[j][l];
				for(int j=lef[bel[p[i].l-1]];j<=p[i].l-1;j++) ans[i]+=DS::blc.query(a[j]-1);
			}
		}
		for(int i=l;i<=r;i++) DS::blc.add(a[i],-(r-i+1));
	}
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) bel[i]=qbel(i);
	for(int i=1;i<=bel[n];i++) lef[i]=qlef(i),rig[i]=qrig(i); 
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&c[i]);
		lis[i]=a[i];
		sc[i]=sc[i-1]+c[i];
	}
	sort(lis+1,lis+n+1);
	clis=unique(lis+1,lis+n+1)-lis-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lis+1,lis+clis+1,a[i])-lis;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&p[i].x,&p[i].d);
		p[i].l=lower_bound(sc+1,sc+n+1,sc[p[i].x-1]+p[i].d)-sc;
		p[i].r=upper_bound(sc+1,sc+n+1,sc[p[i].x-1]+p[i].d)-sc-1;
//		printf("%lld %lld\n",p[i].l,p[i].r);
		if(p[i].r<=p[i].x) continue;
		if(p[i].x<=p[i].l-1&&p[i].l<=p[i].r) q[++cq].l=p[i].x,q[cq].r=p[i].l-1,q[cq].Id=i;
		if(p[i].l<=p[i].r) gId[p[i].l].push_back(i);
	}
	PART_1();
	PART_2();
	for(int i=1;i<=m;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}