P3157 [CQOI2011]动态逆序对
CF785E Anton and Permutation
P1975 [国家集训队]排队
三合一，算法一致，都被我用树套树卡过去了。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5+10;
ll num[MAXN << 7], ans;
int ls[MAXN << 7], rs[MAXN << 7], rt[MAXN], tot, N, M, val[MAXN], where[MAXN];
ll ask(int, int, int, int);
void ins(int&, int, int, int, int);
ll que(int, int, int, int, int);
void upd(int, int, int);
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++) {
scanf("%d", val+i);
upd(i, val[i], 1);
where[val[i]] = i;
}
for (int i = 1; i <= N; i++) ans += ask(1, i, val[i]+1, N);
for (int i = 1, x; i <= M; i++) {
scanf("%d", &x);
x = where[x];
printf("%lld
", ans);
ans -= ask(1, x-1, val[x]+1, N);
ans -= ask(x+1, N, 1, val[x]-1);
upd(x, val[x], -1);
}
return 0;
}
void upd(int x, int y, int v) {for (; x <= N; x += (x & (-x))) ins(rt[x], 1, N, y, v);}
void ins(int &node, int l, int r, int pos, int v) {
if (!node) node = ++tot;
num[node] += v;
if (l == pos && pos == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) ins(ls[node], l, mid, pos, v);
else ins(rs[node], mid+1, r, pos, v);
}
ll ask(int l, int r, int a, int b) {
l--;ll ret = 0;
for (; l; l -= (l & (-l))) ret -= que(rt[l], 1, N, a, b);
for (; r; r -= (r & (-r))) ret += que(rt[r], 1, N, a, b);
return ret;
}
ll que(int node, int l, int r, int a, int b) {
if (!node) return 0;
if (r < a || l > b) return 0;
if (a <= l && r <= b) return num[node];
int mid = (l + r) >> 1; ll ret = 0;
if (a <= mid) ret += que(ls[node], l, mid, a, b);
if (mid < b) ret += que(rs[node], mid+1, r, a, b);
return ret;
}
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef int ll;
const ll MAXM = 2e6+10, MAXN = 2e5+10;
ll N, M, val[MAXN], rt[MAXN], tot;
ll ls[MAXN << 7], rs[MAXN << 7];
long long num[MAXN << 7], ans;
long long ask(ll, ll, ll, ll);
void ins(ll&, ll, ll, ll, ll);
long long que(ll, ll, ll, ll, ll);
void upd(ll, ll, ll);
int main() {
scanf("%d%d", &N, &M);
for (ll i = 1; i <= N; i++)
val[i] = i, upd(i, i, 1);
for (ll i = 1, l, r; i <= M; i++) {
scanf("%d%d", &l, &r);
ans -= ask(l+1, r-1, 1, val[l]-1);
ans += ask(l+1, r-1, val[l]+1, N);
ans += ask(l+1, r-1, 1, val[r]-1);
ans -= ask(l+1, r-1, val[r]+1, N);
if (val[l] < val[r]) ans++;
if (val[l] > val[r]) ans--;
upd(l, val[l], -1);
upd(r, val[r], -1);
swap(val[l], val[r]);
upd(l, val[l], 1);
upd(r, val[r], 1);
printf("%lld
", ans);
}
return 0;
}
void upd(ll x, ll y, ll v) {for (; x <= N; x += (x & (-x))) ins(rt[x], 1, N, y, v);}
void ins(ll &node, ll l, ll r, ll pos, ll v) {
if (!node) node = ++tot;
num[node] += v;
if (pos == l && pos == r) return;
ll mid = (l + r) >> 1;
if (pos <= mid) ins(ls[node], l, mid, pos, v);
else ins(rs[node], mid+1, r, pos, v);
}
long long ask(ll l, ll r, ll a, ll b) {
l--; long long ret = 0;
for (; l; l -= (l & (-l))) ret -= que(rt[l], 1, N, a, b);
for (; r; r -= (r & (-r))) ret += que(rt[r], 1, N, a, b);
return ret;
}
long long que(ll node, ll l, ll r, ll a, ll b) {
if (b < l || r < a || !node) return 0;
if (a <= l && r <= b) return num[node];
ll mid = (l + r) >> 1; long long ret = 0;
if (a <= mid) ret += que(ls[node], l, mid, a, b);
if (mid < b) ret += que(rs[node], mid+1, r, a, b);
return ret;
}
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+10;
ll N, M, h[MAXN], rt[MAXN], tot, ans, SIZ;
vector <ll> q;
struct nod {
ll l, r, val;
} t[MAXN << 1];
struct tr {
ll C[MAXN];
void add(ll x, ll val) {
while (x <= N) {
C[x] += val;
x += (x & (-x));
}
}
ll ask(ll x) {
ll ret = 0;
while (x) {
ret += C[x];
x -= (x & (-x));
}
return ret;
}
} arr;
ll ask(ll, ll, ll, ll);
void updata(ll, ll, ll);
void ins(ll&, ll, ll, ll, ll);
ll t_ask(ll, ll, ll, ll, ll);
int main() {
scanf("%lld", &N);
for (ll i = 1; i <= N; i++)
scanf("%lld", h+i), q.push_back(h[i]);
sort(q.begin(), q.end());
q.erase(unique(q.begin(), q.end()), q.end());
for (ll i = 1; i <= N; i++) h[i] = lower_bound(q.begin(), q.end(), h[i]) - q.begin() + 1;
SIZ = q.size();
for (ll i = 1; i <= N; i++) {
ans += (i - arr.ask(h[i]) - 1);
arr.add(h[i], 1);
updata(i, h[i], 1);
}
printf("%lld
", ans);
scanf("%lld", &M);
for (ll i = 1, a, b; i <= M; i++) {
scanf("%lld%lld", &a, &b);
if (a > b) swap(a, b);
ans -= ask(a+1, b-1, 1, h[a]-1);
ans += ask(a+1, b-1, h[a]+1, SIZ);
ans += ask(a+1, b-1, 1, h[b]-1);
ans -= ask(a+1, b-1, h[b]+1, SIZ);
if (h[a] < h[b]) ans++;
if (h[a] > h[b]) ans--; // if equal, no change
updata(a, h[a], -1);
updata(b, h[a], 1);
updata(b, h[b], -1);
updata(a, h[b], 1);
swap(h[a], h[b]);
printf("%lld
", ans);
}
return 0;
}
ll ask(ll l, ll r, ll a, ll b) {
l--; ll ret = 0;
for (; r; r -= (r & (-r))) ret += t_ask(rt[r], 1, SIZ, a, b);
for (; l; l -= (l & (-l))) ret -= t_ask(rt[l], 1, SIZ, a, b);
return ret;
}
void updata(ll x, ll val, ll v) {for (; x <= N; x += (x & (-x))) ins(rt[x], 1, SIZ, val, v);}
void ins(ll &node, ll l, ll r, ll pos, ll val) {
if (!node) node = ++tot;
t[node].val += val;
if (pos == l && r == pos) return;
ll mid = (l + r) >> 1;
if (pos <= mid) ins(t[node].l, l, mid, pos, val);
else ins(t[node].r, mid+1, r, pos, val);
}
ll t_ask(ll node, ll l, ll r, ll a, ll b) {
if (!node) return 0;
if (r < a || b < l) return 0;
if (a <= l && r <= b) return t[node].val;
ll mid = (l + r) >> 1, ret = 0;
if (a <= mid) ret += t_ask(t[node].l, l, mid, a, b);
if (mid < b) ret += t_ask(t[node].r, mid+1, r, a, b);
return ret;
}