社区讨论

神秘 WA 0pts 求救

P3157[CQOI2011] 动态逆序对参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mk8coux7
此快照首次捕获于
2026/01/10 21:38
上个月
此快照最后确认于
2026/01/14 09:45
上个月
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n, m, p[100005], rid[100005], res[100005];
struct node{
    int x, y, z, ans;
}a[100005];
int lowbit(int x){
	return x & -x;
}
struct BIT{
	int n, tr[100005];
	void upd(int u, int x){
		for (; u <= n; u += lowbit(u))
			tr[u] += x;
	}
	int qry(int u){
		int res = 0;
		for (; u; u -= lowbit(u))
			res += tr[u];
		return res;
	}
}Bit;
bool cmp(node a, node b){
    if (a.x != b.x)
		return a.x < b.x;
    else if (a.y != b.y)
		return a.y < b.y;
	else
    	return a.z < b.z;
}
bool noxcmp(node a, node b){
    if (a.y != b.y)
		return a.y < b.y;
	else
    	return a.z < b.z;
}
void CDQ(int l, int r){
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	CDQ(l, mid);
	CDQ(mid + 1, r);
	sort(a + l, a + mid + 1, noxcmp);
	sort(a + mid + 1, a + r + 1, noxcmp);
	int u = mid + 1;
    for (int i = l; i <= mid; i++){
		while (a[u].y < a[i].y && u <= r){
			Bit.upd(a[u].z, 1);
			u++;
		}
		a[i].ans += Bit.qry(n) - Bit.qry(a[i].z);
	}
	for (int i = mid + 1; i < u; i++)
		Bit.upd(a[i].z, -1);
	reverse(a + l, a + mid + 1);
	reverse(a + mid + 1, a + r + 1);
	u = l;
    for (int i = mid + 1; i <= r; i++){
		while (a[u].y > a[i].y && u <= mid){
			Bit.upd(a[u].z, 1);
			u++;
		}
		a[i].ans += Bit.qry(n) - Bit.qry(a[i].z);
	}
	for (int i = l; i < u; i++)
		Bit.upd(a[i].z, -1);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n >> m;
    Bit.n = m + 1;
    for (int i = 1; i <= n; i++){
    	cin >> p[i];
    	rid[p[i]] = i;
    	a[i].x = i;
    	a[i].y = p[i];
	}
	for (int i = 1; i <= m; i++){
		int x;
		cin >> x;
		a[rid[x]].z = i;
	}
	for (int i = 1; i <= n; i++){
		if (!a[i].z)
			a[i].z = m + 1;
	}
	sort(a + 1, a + 1 + n, cmp);
	CDQ(1, n);
//	for (int i = 1; i <= n; i++)
//		cout << a[i].ans << "\n";
	for (int i = 1; i <= n; i++)
		res[a[i].z - 1] += a[i].ans;
	for (int i = m - 1; ~i; i--)
		res[i] += res[i + 1];
	for (int i = 0; i < m; i++)
		cout << res[i] << "\n"; 
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...