T1 区间颜色查询

solution

首先在查询的区间中一种颜色若能对答案产生贡献，那么 $last_i <= l$ ($last_i$ 为此颜色上一次出现的下标，$l$ 为当前区间左端点)，所以可以预处理出 $last_i$ 的值

随后我们可以考虑离线处理，将查询区间按右端点排序，先从右边将所有的第一次出现的数加 $1$，随后枚举区间，若上一个区间右端点为 $r'$，当前区间右端点为 $r$，则需要将 $(r,r']$ 区间内的颜色的前一个相同的颜色加 $1$，随后对当前区间求和即可

注意到我们对数列的操作有两种：

1. 单点修改
2. 区间查询

所以可用树状数组优化

code

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 5e5 + 5;

struct ask{
	int l , r , id;
}a[N];

int n , q;
int c[N] , tr[N] , res[N] , last[N] , to[N];

bool cmp(const ask &lhs , const ask &rhs){
	if(lhs.r == rhs.r) return lhs.l > rhs.l;
	return lhs.r > rhs.r;
}

int lowbit(int x){
	return x & (-x);
}

void modify(int x , int k){
	while(x <= n){
		tr[x] += k;
		x += lowbit(x);
	}
}

int query(int x){
	int s = 0;
	while(x){
		s += tr[x];
		x -= lowbit(x);
	}
	return s;
}

int main(){            qwq
	cin >> n >> q;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> c[i];
		
		if(to[c[i]]) last[i] = to[c[i]];
		to[c[i]] = i;
	}
	for(int i = 1 ; i <= q ; i ++){
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
	}
	sort(a + 1 , a + q + 1 , cmp);
	
	for(int i = 1 ; i <= n ; i ++){
		if(to[c[i]] == i) modify(i , 1);
	}
	int lt = n;
	for(int i = 1 ; i <= q ; i ++){
		while(lt > a[i].r){
			if(last[lt] > 0){
				modify(last[lt] , 1);
			}
			lt --;
		}
		res[a[i].id] = query(a[i].r) - query(a[i].l - 1);
	}
	for(int i = 1 ; i <= q ; i ++){
		cout << res[i] << '\n';
	}
	return 0;
}

T2 嫉妒的两人

solution

先将题意简化一下，就是求所有的数对 $(i , j)$ 满足 $a_i \geq a_j \& b_i \leq b_j$ 的数量

可以先将 $a,b$ 数组看作一个整体，按 $a$ 从小到大为第一关键字， $b$ 从大到小为第二关键字排序

可以枚举 $i$ 看有多少 $j$ 满足要求，因为 $a$ 数组从小到大排序了，所以只用看 $b$ 中有多少个数满足 $b_i \leq b_j$ 即可（注意这里的数也要满足 $a$ 数组的条件）

所以我们在枚举 $i$ 时随便标记 $b$ 数组的数，查询比 $b_i$ 大的数的数量累加即可，此过程可用树状数组优化

注意两点：

1. $0 \leq b_i \leq 10^9$ 所以要对 $b$ 数组离散化
2. 要处理相同数字的情况

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 5;

struct node{
	ll a , b;
}p[N];

ll n , ans , alls[N] , idx , tr[N];

bool cmp(const node &lhs , const node &rhs){
	if(lhs.a == rhs.a) return lhs.b > rhs.b;
	return lhs.a < rhs.a;
}

int lowbit(int x){
	return x & (-x);
}

int query(int x){
	int s = 0;
	while(x){
		s += tr[x];
		x -= lowbit(x);
	}
	return s;
}

void modify(int x , int k){
	while(x <= n){
		tr[x] += k;
		x += lowbit(x);
	}
}

int bs(int x){
	int l = 1 , r = idx;
	while(l < r){
		int mid = (l + r) >> 1;
		if(alls[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}

signed main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> p[i].a;
	}
	for(int i = 1 ; i <= n ; i ++){
		cin >> p[i].b;
		alls[i] = p[i].b;
	}
	sort(p + 1 , p + n + 1 , cmp);
	sort(alls + 1 , alls + n + 1);
	
	idx = unique(alls + 1 , alls + n + 1) - (alls + 1);
	
	for(int i = 1 ; i <= n ; i ++){
		ll same = 1;
		while(i < n && p[i].a == p[i + 1].a && p[i].b == p[i + 1].b){
			same ++ , i ++;
		}
		
		ll nb = bs(p[i].b);
		ll cnt = query(idx) - query(nb - 1);
		ans += cnt * same + same * same;
		modify(nb , same);
	}
	cout << ans;
	return 0;
}

T4 矩阵操作

solution

首先考虑只有操作 1,3 的情况，此时直接用树状数组维护每一列的和即可

如果有操作 2 ，我们要想办法消除操作 2 的影响，容易发现，操作 2 的影响是按照时间顺序的，所以可以将所有操作离线考虑

1. 对于操作 1 直接存储即可
2. 对于操作 2 ，用桶数组记录每个操作 2 在什么时间将哪一行变为了什么，桶数组下标就是操作 2 所影响的行
3. 对于操作 3 ，也可以用桶数组记录每一个操作 2 影响了那些操作 3

随后直接模拟即可，具体地：

1. 操作 1 ：树状数组直接处理区间加
2. 操作 2 ：对于每个被此操作 2 影响的操作 3 减去之前的累加结果
3. 操作 3 ：直接加当前列的值即可

code

#include<bits/stdc++.h>
#define int long long
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 2e5 + 5;

struct oper1{
	int l , r , d;
}p1[N];

struct oper2{
	int i , x;
}p2[N];

struct oper3{
	int i , j , id;
}p3[N];

struct node{
	int x , t;
}h[N];

int n , m , q , op[N] , res[N] , cnt , tr[N];
vector<int> g[N];

int lowbit(int x){
	return x & (-x);
}

void modify(int x , int k){
	while(x <= m){
		tr[x] += k;
		x += lowbit(x);
	}
}

int query(int x){
	int s = 0;
	while(x){
		s += tr[x];
		x -= lowbit(x);
	}
	return s;
}

signed main(){                  qwq
	cin >> n >> m >> q;
	
	for(int i = 1 ; i <= q ; i ++){
		cin >> op[i];
		
		if(op[i] == 1){
			cin >> p1[i].l >> p1[i].r >> p1[i].d;
		}
		if(op[i] == 2){
			cin >> p2[i].i >> p2[i].x;
			h[p2[i].i] = {p2[i].x , i};
		}
		if(op[i] == 3){
			cin >> p3[i].i >> p3[i].j;
			p3[i].id = ++ cnt;
			
			res[cnt] = h[p3[i].i].x;
			g[h[p3[i].i].t].push_back(i);
		}
	}
	for(int i = 1 ; i <= q ; i ++){
		if(op[i] == 1){
			modify(p1[i].l , p1[i].d);
			modify(p1[i].r + 1 , -p1[i].d);
		}
		if(op[i] == 2){
			for(int j = 0 ; j < g[i].size() ; j ++){
				res[p3[g[i][j]].id] -= query(p3[g[i][j]].j);
			}
		}
		if(op[i] == 3){
			res[p3[i].id] += query(p3[i].j);
		}
	}
	for(int i = 1 ; i <= cnt ; i ++){
		cout << res[i] << endl;
	}
	return 0;
}

T5 交换

solution

题目中的操作执行完后容易发现 $a_i + i$ 为定值，所以可以将原 a,b 数组每个值加上 $i$，操作就转化为交换 a 数组相邻两个数的位置

若 a,b 数组的值有不相同的，则不可能通过操作将 a 数组转化为 b 数组，此时答案为 $-1$

若都为相同可以标记每个 b 数组中的元素对应 a 数组元素的下标，用一个数组 f 记录这些下标，于是答案就转化为求 f 数组的逆序对数量，用树状数组或者分治即可

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 5;

ll n , a[N] , b[N] , a1[N] , b1[N] , f[N] , tr[N];
map<ll , vector<int> > mp;

ll lowbit(int x){
	return x & (-x);
}

void modify(int x , int k){
	while(x <= n){
		tr[x] += k;
		x += lowbit(x);
	}
}

ll query(int x){
	int s = 0;
	while(x){
		s += tr[x];
		x -= lowbit(x);
	}
	return s;
}

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		
		a[i] += i;
		a1[i] = a[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		cin >> b[i];
		
		b[i] += i;
		b1[i] = b[i];
	}
	sort(a1 + 1 , a1 + n + 1);
	sort(b1 + 1 , b1 + n + 1);
	
	for(int i = 1 ; i <= n ; i ++){
		if(a1[i] != b1[i]){
			cout << "-1";
			return 0;
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		mp[b[i]].push_back(i);
	}
	for(int i = 1 ; i <= n ; i ++){
		f[i] = mp[a[i]].front();
		mp[a[i]].erase(mp[a[i]].begin());
	}
	ll ans = 0;
	for(int i = n ; i >= 1 ; i --){
		ans += query(f[i]);
		modify(f[i] , 1);
	}
	cout << ans;
	return 0;
}