嘛，好久没碰CDQ分治了，做道题练练手。
时间倒流——把删数改为加数。
对于每个被删的，我的想法是拆成询问和add，后来发现一个足矣。
我本来准备对每个删的数都求一遍整体逆序对，后来发现无论如何都不可做。
然后发现是只求改的逆序对，做两次CDQ，一次统计在前面大的，一次统计在后面小的。
注意：这两次的区别是id那一维的顺序不同，而time顺序是相同的。
记得离散化。
然后我打完 + 静态差错之后，一发过样例AC，稳！！！
顺手切了一模一样的3157，WA了两个点。发现输出负数......换成longlong之后AC。
#include <cstdio>
#include <algorithm>
#include <cstring> typedef long long LL; const LL N = ; LL x[N], a[N], n; struct TreeArray {
LL tr[N];
inline void clear() {
memset(tr, , sizeof(tr));
return;
}
inline void add(LL x, LL a) {
for(; x < N; x += x & (-x)) {
tr[x] += a;
}
return;
}
inline LL getsum(LL x) {
LL ans = ;
for(; x; x -= x & (-x)) {
ans += tr[x];
}
return ans;
}
inline LL ask(LL l, LL r) {
if(l == ) {
return getsum(r);
}
return getsum(r) - getsum(l - );
}
}ta; struct Node {
LL val, ans, time, type, id;
}node[N], temp[N]; inline bool cmp_t(Node d, Node e) {
return d.time < e.time;
}
inline bool cmp__t(Node d, Node e) {
return d.time > e.time;
} void CDQ1(LL l, LL r) {
if(l == r) {
return;
}
LL mid = (l + r) >> ;
CDQ1(l, mid);
CDQ1(mid + , r); LL i = l, j = mid + , t = ;
while(i <= mid || j <= r) {
if(j > r || (i <= mid && node[i].id < node[j].id)) {
ta.add(node[i].val, );
temp[++t] = node[i++];
}
else {
if(node[j].type == ) {
node[j].ans += ta.ask(node[j].val + , n);
}
temp[++t] = node[j++];
}
}
for(i = l; i <= mid; i++) {
ta.add(node[i].val, -);
}
t = ;
for(LL i = l; i <= r; i++) {
node[i] = temp[++t];
}
return;
} void CDQ2(LL l, LL r) {
if(l == r) {
return;
}
LL mid = (l + r) >> ;
CDQ2(l, mid);
CDQ2(mid + , r); LL i = l, j = mid + , t = ;
while(i <= mid || j <= r) {
if(j > r || (i <= mid && node[i].id > node[j].id)) { /// error : id < id
ta.add(node[i].val, 1);/// error : if(type == 1)
temp[++t] = node[i++];
}
else {
if(node[j].type == ) {
node[j].ans += ta.getsum(node[j].val - );
}
temp[++t] = node[j++];
}
}
for(i = l; i <= mid; i++) {
ta.add(node[i].val, -);/// error : if(type == 1)
}
t = ;
for(i = l; i <= r; i++) {
node[i] = temp[++t];
}
return;
} LL pos[N]; int main() {
LL m;
scanf("%lld%lld", &n, &m);
for(LL i = ; i <= n; i++) {
scanf("%lld", &a[i]);
x[i] = a[i];
node[i].id = i;
node[i].type = ; /// normal
}
std::sort(x + , x + n + );
LL xx = std::unique(x + , x + n + ) - x - ;
for(LL i = ; i <= n; i++) {
LL p = std::lower_bound(x + , x + xx + , a[i]) - x;
node[i].val = p;
pos[p] = i;
}
/// li san hua wan bi LL nn = n, p;
for(LL i = ; i <= m; i++) {
scanf("%lld", &p);
p = std::lower_bound(x + , x + xx + , p) - x;
p = pos[p];
node[p].type = ; /// add
node[p].time = nn--;
}
for(LL i = ; i <= n; i++) {
if(node[i].type == ) {
node[i].time = nn--;
}
}
LL ans = ;
for(LL i = ; i <= n; i++) {
if(node[i].type == ) {
ans += ta.ask(node[i].val + , n);
ta.add(node[i].val, );
}
}
ta.clear();
std::sort(node + , node + n + , cmp_t);
CDQ1(, n);
std::sort(node + , node + n + , cmp_t); /// error : cmp__t -> cmp_t
CDQ2(, n);
std::sort(node + , node + n + , cmp__t);
for(LL i = ; i <= m; i++) {
ans += node[i].ans;
}
for(LL i = ; i <= m; i++) {
printf("%lld\n", ans);
ans -= node[i].ans;
}
return ;
}
P3157
#include <cstdio>
#include <algorithm>
#include <cstring> const int N = ; int x[N], a[N], n; struct TreeArray {
int tr[N];
inline void clear() {
memset(tr, , sizeof(tr));
return;
}
inline void add(int x, int a) {
for(; x < N; x += x & (-x)) {
tr[x] += a;
}
return;
}
inline int getsum(int x) {
int ans = ;
for(; x; x -= x & (-x)) {
ans += tr[x];
}
return ans;
}
inline int ask(int l, int r) {
if(l == ) {
return getsum(r);
}
return getsum(r) - getsum(l - );
}
}ta; struct Node {
int val, ans, time, type, id;
}node[N], temp[N]; inline bool cmp_t(Node d, Node e) {
return d.time < e.time;
}
inline bool cmp__t(Node d, Node e) {
return d.time > e.time;
} void CDQ1(int l, int r) {
if(l == r) {
return;
}
int mid = (l + r) >> ;
CDQ1(l, mid);
CDQ1(mid + , r); int i = l, j = mid + , t = ;
while(i <= mid || j <= r) {
if(j > r || (i <= mid && node[i].id < node[j].id)) {
ta.add(node[i].val, );
temp[++t] = node[i++];
}
else {
if(node[j].type == ) {
node[j].ans += ta.ask(node[j].val + , n);
}
temp[++t] = node[j++];
}
}
for(i = l; i <= mid; i++) {
ta.add(node[i].val, -);
}
t = ;
for(int i = l; i <= r; i++) {
node[i] = temp[++t];
}
return;
} void CDQ2(int l, int r) {
if(l == r) {
return;
}
int mid = (l + r) >> ;
CDQ2(l, mid);
CDQ2(mid + , r); int i = l, j = mid + , t = ;
while(i <= mid || j <= r) {
if(j > r || (i <= mid && node[i].id > node[j].id)) {
ta.add(node[i].val, );
temp[++t] = node[i++];
}
else {
if(node[j].type == ) {
node[j].ans += ta.getsum(node[j].val - );
}
temp[++t] = node[j++];
}
}
for(i = l; i <= mid; i++) {
ta.add(node[i].val, -);
}
t = ;
for(i = l; i <= r; i++) {
node[i] = temp[++t];
}
return;
} int main() {
int m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
x[i] = a[i];
node[i].id = i;
node[i].type = ; /// normal
}
std::sort(x + , x + n + );
int xx = std::unique(x + , x + n + ) - x - ;
for(int i = ; i <= n; i++) {
int p = std::lower_bound(x + , x + xx + , a[i]) - x;
node[i].val = p;
}
/// li san hua wan bi int nn = n;
for(int i = ; i <= m; i++) {
scanf("%d", &xx);
node[xx].type = ; /// add
node[xx].time = nn--;
}
for(int i = ; i <= n; i++) {
if(node[i].type == ) {
node[i].time = nn--;
}
}
int ans = ;
for(int i = ; i <= n; i++) {
if(node[i].type == ) {
ans += ta.ask(node[i].val + , n);
ta.add(node[i].val, );
}
}
ta.clear();
std::sort(node + , node + n + , cmp_t);
CDQ1(, n);
std::sort(node + , node + n + , cmp_t);
CDQ2(, n);
std::sort(node + , node + n + , cmp__t);
for(int i = ; i <= m; i++) {
ans += node[i].ans;
}
for(int i = ; i <= m + ; i++) {
printf("%d ", ans);
ans -= node[i].ans;
}
return ;
}
P1393
CDQ大法好！