嫉妒的两人

这两个人没事找事

心眼真小

有礼物了还计较这些

思路

我们发现，一组满足条件的$(i,j)$需要满足以下条件

1.$a_i \geq a_j$

2.$b_i \leq a_j$

其实我们只需要给$a$排一下序，就可以满足第一个条件

然后我们先不考虑特殊点，发现对一个$i$的点要增加的ans：

$$ans=i-ask(a_i)$$

接着我们考虑$a_i=a_j$的情况（允许$i=j$）发现如果有$cnt$个重复的$a_i$那么将增加$cnt^2$的方式，ans也要变成：

$$ans=(i-ask(a_i))\times cnt$$

最后$i$点加上的值是

$$sum+=cnt+ans$$

记得离散化哦~

千万不要用map

会超时的

我就超了

双倍求和

这真的只是求和吗

思路

题目给的公式

$$S_n=a\sum\limits_{i=1}^N\sum\limits_{j=i+1}^Nmax(A_j-A_i,0)$$

所以说，我们求出每个$i$前面所有比他小的和，累加即可

矩阵操作

第二个操作真的太%#$@

我们发现，第二个操作实在是太恶心了烦死了，但我们可以用一个动态数组记录一下一操作，如果遇到了二操作的更改值，就可以对改的那行标记，让之前的一操作不在其作用，然后继续

当查询的时候，我们就拿出那个标记，去和已操作的动态数组操作，得到答案

#include<bits/stdc++.h>
using namespace std;
const int  N=2e5+10;
long long tr[N];
void add(int x,long long c,int n){
	for(int i=x;i<=n;i+=(i&-i))tr[i]+=c;
}
long long cx(int x){
	long long res=0;
	for(int i=x;i;i-=(i&-i))res+=tr[i];
	return res;
}
int t[N],a[N],b[N];
long long c[N];
vector<int>subt[N];
pair<int,long long>la[N];
long long ans[N];
int su=0;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<n;++i){
		la[i]={-1,0};
	}
	for(int i=1;i<=q;i++){
		cin>>t[i];
		if(t[i]==1){
			cin>>a[i]>>b[i]>>c[i];
		}
		else if(t[i]==2){
			cin>>a[i]>>c[i];
			la[a[i]]={i,c[i]};
		}
		else{
			cin>>a[i]>>b[i];
			auto[j,x]=la[a[i]];
			ans[su]=x;
			c[i]=su++;
			if(j>=1){
				subt[j].push_back(i);
			}
		}
	}
	memset(tr,0,sizeof(tr));
	for(int i=1;i<=q;++i){
		if(t[i]==1){
			add(a[i],c[i],m);
			add(b[i]+1,-c[i],m);
		}
		else if(t[i]==2){
			for(int j:subt[i])ans[c[j]]-=cx(b[j]);
		}
		else{
			ans[c[i]]+=cx(b[i]);
		}
	}
	
	for(int i=0;i<su;++i){
		cout<<ans[i]<<'\n';
	}
	
	return 0;
}

交换

很简单的

思路

首先我们先分析下这几个可爱的步骤

1. 交换$A_i,A_i+1$
2. 将$A_i$加$1$
3. 将$A_i+1$减$1$

我们发现了一个奇妙的规律：

$$每个数加他下标不变$$ $$a_i+i不变$$

所以我们能得出两个数组的$a_i+i$都要一一对应，这可以判断出是否可以得出另外一个数组

那要多少步呢？

把a中值为$k$的映射到b中值为$k$的下标，并按下表为只存入数组$c$，c的值与$1~n$一一对应，而要变成的数组可以表示为$1~n$,所以要把数组变成目标，就相当于把$c$变成顺序的$1~n$也就是求c得逆序对