danihao123's Blog

又一道坑了很久没有写题解的……

删除操作特别的棘手，但好在我们可以离线~时光倒流之后，删除就变成了添加。

每个点加进来之后，对答案的贡献可以分为两部分：

1. 加入比他早，位置在他前面，值比他大的点。
2. 加入比他早，位置在他后面，值比他小的点。

然后两者都可以用CDQ统计（我还偷懒用同一个CDQ做的）。

代码：

/**************************************************************
    Problem: 3295
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2332 ms
    Memory:5768 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using std::stack;
using std::sort;
const int maxn = 100005;
typedef long long ll;
struct Query {
    int id;
    int p, v;
};
 
int n;
ll C[maxn];
int lowbit(int x) {
    return x & (-x);
}
void add(int p, int v) {
    while(p <= n) {
        C[p] += v;
        p += lowbit(p);
    }
}
ll sum(int p) {
    ll ret = 0;
    while(p > 0) {
        ret += C[p];
        p -= lowbit(p);
    }
    return ret;
}
int query(int l, int r) {
    return sum(r) - sum(l - 1);
}
void clean(int p) {
    while(p <= n && C[p] != 0) {
        C[p] = 0;
        p += lowbit(p);
    }
}
 
Query A[maxn], tmp[maxn];
ll ans[maxn];
void CDQ(int L, int R, bool flag) {
    if(L == R) {
        return;
    }
    int M = L + (R - L) / 2;
    CDQ(L, M, flag); CDQ(M + 1, R, flag);
    for(int p = L, l = L, r = M + 1; p <= R; p ++) {
        if(r > R || (l <= M && (flag ? A[l].p < A[r].p : A[l].p > A[r].p))) {
            tmp[p] = A[l];
            add(A[l].v, 1);
            l ++;
        } else {
            tmp[p] = A[r];
            ans[A[r].id] += query(A[r].v + 1, n);
            r ++;
        }
    }
    for(int i = L; i <= M; i ++) {
        clean(A[i].v);
    }
    for(int i = L; i <= R; i ++) {
        A[i] = tmp[i];
    }
}
bool cmp_id(const Query& a, const Query& b) {
    return a.id < b.id;
}
 
int arr[maxn];
bool del[maxn];
int pos[maxn];
stack<int> delS;
int main() {
    int m;
    scanf("%d%d", &n, &m);
    int id_siz = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= m; i ++) {
        int a;
        scanf("%d", &a);
        delS.push(a);
        del[a] = true;
    }
    for(int i = 1; i <= n; i ++) {
        if(del[arr[i]]) {
            pos[arr[i]] = i;
        } else {
            id_siz ++;
            A[id_siz].id = id_siz;
            A[id_siz].p = i;
            A[id_siz].v = arr[i];
        }
    }
    while(!delS.empty()) {
        int a = delS.top(); delS.pop();
        id_siz ++;
        A[id_siz].id = id_siz;
        A[id_siz].p = pos[a];
        A[id_siz].v = a;
    }
    CDQ(1, n, true);
    sort(A + 1, A + 1 + n, cmp_id);
    for(int i = 1; i <= n; i ++) {
        A[i].v = n - A[i].v + 1;
    }
    CDQ(1, n, false);
    for(int i = 1; i <= n; i ++) {
        ans[i] += ans[i - 1];
    }
    for(int i = 0; i < m; i ++) {
        printf("%lld\n", ans[n - i]);
    }
    return 0;
}

CDQ分治第一题……同时也是CDQ分治模板提。

感觉CDQ分治思路好秒啊……似乎在分治过程中做了个归并排序……

代码：

/**************************************************************
    Problem: 1176
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4364 ms
    Memory:17228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxw=2000005;
const int maxq=10005;
const int maxn=160001+4*maxq;
int cnt=0;
struct Query{
  int ans_id;
  int x,y,d,v;
  Query(){}
  Query(int a,int b,int di,int ap){
    x=a;y=b;
    d=di;
    ans_id=ap;
  }
  Query(int a,int b,int value){
    x=a;y=b;
    v=value;
    d=0;
  }
  inline bool isQuery(){
    return d!=0;
  }
};
 
int w;
int T[maxw];
inline int lowbit(int x){
  return x&(-x);
}
inline void add(int p,int v){
  while(p<=w){
    T[p]+=v;
    p+=lowbit(p);
  }
}
inline int sum(int p){
  register int x=0;
  while(p>0){
    x+=T[p];
    p-=lowbit(p);
  }
  return x;
}
inline void clear(int p){
  while(p<=w && T[p]!=0){
    T[p]=0;
    p+=lowbit(p);
  }
}
 
Query Q[maxn],tmp[maxn];
int ans[maxn];
void CDQ(int L,int R){
  if(L==R){
    return;
  }
  int M=L+(R-L)/2;
  CDQ(L,M);
  CDQ(M+1,R);
  int p,p1,p2;
  for(p=1,p1=L,p2=M+1;p<=(R-L+1);p++){
    if((Q[p1].x<=Q[p2].x && p1<=M) || p2>R){
      tmp[p]=Q[p1];
      if(!Q[p1].isQuery()){
        add(Q[p1].y,Q[p1].v);
      }
      p1++;
    }else{
      tmp[p]=Q[p2];
      if(Q[p2].isQuery()){
        ans[Q[p2].ans_id]+=sum(Q[p2].y)*Q[p2].d;
      }
      p2++;
    }
  }
  for(p=1,p1=L;p<=(R-L+1);p++,p1++){
    if(!Q[p1].isQuery()){
      clear(Q[p1].y);
    }
    Q[p1]=tmp[p];
  }
}
 
int main(){
  int S,t,x,y,a,b;
  register int ans_cnt=0;
  scanf("%d%d",&S,&w);
  while(true){
    scanf("%d",&t);
    if(t==3){
      break;
    }
    scanf("%d%d%d",&x,&y,&a);
    // x++;y++;
    if(t==1){
      Q[++cnt]=Query(x,y,a);
    }else{
      scanf("%d",&b);
      // a++;b++;
      ans_cnt++;
      ans[ans_cnt]=(a-x+1)*(b-y+1)*S;
      Q[++cnt]=Query(a,b,1,ans_cnt);
      Q[++cnt]=Query(x-1,b,-1,ans_cnt);
      Q[++cnt]=Query(a,y-1,-1,ans_cnt);
      Q[++cnt]=Query(x-1,y-1,1,ans_cnt);
    }
  }
  CDQ(1,cnt);
  for(register int i=1;i<=ans_cnt;i++){
    printf("%d\n",ans[i]);
  }
  return 0;
}