社区讨论
神秘 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 条回复,欢迎继续交流。
正在加载回复...