HDU 5618 Jam's problem again

Problem Description

N(1≤N≤100000) points

(x,y,z)(1≤x,y,z≤100000)

If two point such as

(xi,yi,zi) and

(xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add

Ask for the each level of the point.

Input

T(1≤T≤15) means

T Case

For each case

The first line is

N means the number of Point and next there are

N line, each line has

(x,y,z)

Output

Output with N line,each line has one number means the lever of point

Sample Input

10 4 7

10 6 6

8 2 5

7 3 10

Sample Output

三維偏序，研究了挺久的，bc的時候因為沒考慮相等的問題最後wa了，真的是。。。

BC的時候寫的樹狀數組套線段樹，缺點是容易爆記憶體，好像資料比較水？

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int low(int x){ return x&-x; }
int T, n;
struct point
{
    int x, y, z, id, cnt;
    void read(){ scanf("%d%d%d", &x, &y, &z); cnt = 0; }
    bool operator<(const point& a) const
    {
        if (x == a.x&&y == a.y) return z < a.z;
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
}a[maxn];

bool cmp(const point&a, const point&b)
{
    return a.id < b.id;
}

struct Tree
{
    int tot, first[maxn], f[maxn * 50], L[maxn * 50], R[maxn * 50], lit, lim;
    void clear(int x, int y)
    {
        lit = x;    lim = y;
        for (int i = 1; i <= lit; i++)
        {
            first[i] = i;
            f[i] = R[i] = L[i] = 0;
        }
        tot = lit + 1;
    }
    int newnode()
    {
        f[tot] = R[tot] = L[tot] = 0;
        return tot++;
    }
    void ins(int x, int l, int r, int v)
    {
        f[x] += 1;
        if (l == r) return;
        int mid = l + r >> 1;
        if (v <= mid) { if (!L[x]) L[x] = newnode(); ins(L[x], l, mid, v); }
        else { if (!R[x]) R[x] = newnode(); ins(R[x], mid + 1, r, v); }
    }
    void insert(int x, int y)
    {
        for (int i = x; i <= lit; i += low(i)) ins(first[i], 1, lim, y);
    }
    int find(int x, int l, int r, int v)
    {
        if (r <= v) return f[x];
        int mid = l + r >> 1, ans = 0;
        if (v <= mid) ans = find(L[x], l, mid, v);
        else ans = f[L[x]] + find(R[x], mid + 1, r, v);
        return ans;
    }
    int get(int x, int y)
    {
        int res = 0;
        for (int i = x; i; i -= low(i)) res += find(first[i], 1, lim, y);
        return res;
    }
}tree;

int main()
{
    scanf("%d", &T);
    while (scanf("%d", &n) != EOF, T--)
    {
        for (int i = 0; i < n; i++) a[i].read(), a[i].id = i;
        sort(a, a + n);
        for (int i = n - 2; i >= 0; i--) 
        if (a[i].x == a[i + 1].x&&a[i].y == a[i + 1].y&&a[i].z == a[i + 1].z) a[i].cnt = a[i + 1].cnt + 1;

        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < n; i++) ans1 = max(ans1, a[i].y), ans2 = max(ans2, a[i].z);
        tree.clear(ans1, ans2);
        for (int i = 0; i < n; i++)
        {
            a[i].cnt += tree.get(a[i].y, a[i].z);
            tree.insert(a[i].y, a[i].z);
        }
        sort(a, a + n, cmp);
        for (int i = 0; i < n; i++) printf("%d\n", a[i].cnt);
    }
    return 0;
}

後來搞定的cdq分治，一維排序，二維分治，三維樹狀數組（四維的話就兩次分治）

#include<iostream>  
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1e5 + 5;
const int low(int x){ return (x&-x); }
int T, n, f[maxn];

struct point
{
    int x, y, z, cnt, id;
    void read(){ scanf("%d%d%d", &x, &y, &z); cnt = 0; }
    bool operator<(const point&a)const
    {
        if (x == a.x&&y == a.y) return z < a.z;
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
    bool operator==(const point&a)const
    {
        return x == a.x&&y == a.y&&z == a.z;
    }
}a[maxn], b[maxn];

bool cmp(const point&a, const point&b)
{
    return a.id < b.id;
}

void add(int x, int y)
{
    for (int i = x; i < maxn; i += low(i)) f[i] += y;
}

int get(int x)
{
    int ans = 0;
    for (int i = x; i; i -= low(i)) ans += f[i];
    return ans;
}

void merge(int l, int r)
{
    if (l == r) return;
    int mid = l + r >> 1;
    merge(l, mid);    merge(mid + 1, r);
    for (int i = l, j = l, k = mid + 1; i <= r; i++)
    {
        if ((a[j].y <= a[k].y || r < k) && j <= mid)
        {
            b[i] = a[j++];
            add(b[i].z, 1);
        }
        else
        {
            b[i] = a[k++];
            b[i].cnt += get(b[i].z);
        }
    }
    for (int i = l; i <= mid; i++) add(a[i].z, -1), a[i] = b[i];
    for (int i = mid + 1; i <= r; i++) a[i] = b[i];
}

int main(){
    scanf("%d", &T);
    while (~scanf("%d", &n), T--)
    {
        for (int i = 0; i < n; i++) a[i].read(), a[i].id = i;
        sort(a, a + n);
        for (int i = n - 2; i >= 0; i--)
            if (a[i] == a[i + 1]) a[i].cnt = a[i + 1].cnt + 1;
        merge(0, n - 1);
        sort(a, a + n, cmp);
        for (int i = 0; i < n; i++) printf("%d\n", a[i].cnt);
    }
    return 0;
}

後來自己鼓搗了一個分塊，也能過去，應該是正确的，時間效率4nlog(n)+2n(sqrt(n)+log^2(sqrt(n)))比cdq稍微慢一點

#include<iostream>  
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 5e2 + 5;
const int low(int x){ return x&-x; }
int T, n, f[maxn][maxn], sqn;

struct point
{
    int x, y, z, cnt, id, by, bz;
    void read(){ scanf("%d%d%d", &x, &y, &z); cnt = 0; }
    bool operator==(const point&a)
    {
        return x == a.x&&y == a.y&&z == a.z;
    }
    bool operator<(const point&a)
    {
        return x <= a.x&&y <= a.y&&z <= a.z;
    }
}a[maxn * 200];

vector<point> p[maxn], q[maxn];

bool cmpx(const point&a, const point&b)
{
    if (a.x == b.x&&a.y == b.y) return a.z < b.z;
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool cmpy(const point&a, const point&b)
{
    if (a.y == b.y) return a.z < b.z;
    return a.y < b.y;
}

bool cmpz(const point&a, const point&b)
{
    if (a.z == b.z) return a.y < b.y;
    return a.z < b.z;
}

bool cmpid(const point&a, const point&b)
{
    return a.id < b.id;
}

void add(int x, int y)
{
    for (int i = x; i <= sqn; i += low(i))
        for (int j = y; j <= sqn; j += low(j)) f[i][j]++;
}

int get(int x, int y)
{
    int ans = 0;
    for (int i = x; i ; i -= low(i))
        for (int j = y; j ; j -= low(j)) ans += f[i][j];
    return ans;
}

int main(){
    scanf("%d", &T);
    while (~scanf("%d", &n), T--)
    {
        memset(f, 0, sizeof(f));
        for (int i = 0; i < n; i++) a[i].read(), a[i].id = i;
        sqn = sqrt(n) + 1;
        for (int i = 1; i <= sqn; i++) p[i].clear(), q[i].clear();
        sort(a, a + n, cmpy);    for (int i = 0; i < n; i++) a[i].by = i / sqn + 1;
        sort(a, a + n, cmpz);    for (int i = 0; i < n; i++) a[i].bz = i / sqn + 1;
        
        sort(a, a + n, cmpx);    for (int i = n - 2; i >= 0; i--) if (a[i] == a[i + 1]) a[i].cnt = a[i + 1].cnt + 1;
        for (int i = 0; i < n; i++)
        {
            int x = a[i].by, y = a[i].bz;
            a[i].cnt += get(x - 1, y - 1);
            for (int j = 0; j < p[x].size(); j++) if (p[x][j] < a[i]) a[i].cnt++;
            for (int j = 0; j < q[y].size(); j++) if (q[y][j] < a[i] && q[y][j].by != x) a[i].cnt++;
            p[x].push_back(a[i]);
            q[y].push_back(a[i]);
            add(x, y);
        }
        sort(a, a + n, cmpid);
        for (int i = 0; i < n; i++) printf("%d\n", a[i].cnt);
    }
    return 0;
}

完全了解了cdq分治的思想以後再寫的不用樹狀數組，直接排序+兩次cdq分治的方法

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int T, n, ans[maxn];

struct point
{
  int x, y, z, fx;
  int *ans;
  void read(){ scanf("%d%d%d", &x, &y, &z); }
  bool operator==(const point&a)const
  {
    return x == a.x&&y == a.y&&z == a.z;
  }
}a[maxn], b[maxn], c[maxn];

bool cmpx(const point&a, const point&b)
{
  return a.x == b.x ? a.y == b.y ? a.z < b.z : a.y < b.y : a.x < b.x;
}

void solve(int l, int r)
{
  if (l == r) return;
  int mid = l + r >> 1;
  solve(l, mid);  solve(mid + 1, r);
  for (int i = l, j = l, k = mid + 1, cnt = 0; i <= r; i++)
  {
    if ((b[j].z <= b[k].z || k>r) && j <= mid) c[i] = b[j++], cnt += c[i].fx ^ 1;
    else { c[i] = b[k++]; if (c[i].fx) *c[i].ans += cnt; }
  }
  for (int i = l; i <= r; i++) b[i] = c[i];
}

void merge(int l, int r)
{
  if (l == r) return;
  int mid = l + r >> 1;
  merge(l, mid);  merge(mid + 1, r);
  for (int i = l, j = l, k = mid + 1; i <= r; i++)
  {
    if ((a[j].y <= a[k].y || k>r) && j <= mid) b[i] = a[j++], b[i].fx = 0;
    else b[i] = a[k++], b[i].fx = 1;
  }
  for (int i = l; i <= r; i++) a[i] = b[i];
  solve(l, r);
}

int main(){
  scanf("%d", &T);
  while (T--)
  { 
    scanf("%d", &n);
    for (int i = 0; i < n; i++) a[i].read(), a[i].ans = &ans[i], ans[i] = 0;
    sort(a, a + n, cmpx);
    for (int i = n - 2; i >= 0; i--)
      if (a[i] == a[i + 1]) *a[i].ans = *a[i + 1].ans + 1;
    merge(0, n - 1);
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  }
  return 0;
}

分塊+bitset的方法，但是會逾時，這個在解決更高維的時候會有特效

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<map>
using namespace std;
const int maxn = 1e5 + 10;
int T, n, sqn, p[maxn][3];
bitset<maxn> ans[3][320], res[3];
map<int, int> M[3];

struct point
{
  int x, id;
  void read(int y){ id = y; scanf("%d", &x); }
  bool operator<(const point&a) { return x == a.x ? id < a.id : x < a.x; }
}a[3][maxn];

int main(){
  scanf("%d", &T);
  while (T--)
  { 
    scanf("%d", &n); 
    sqn = sqrt(n);
    for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) a[j][i].read(i);
    for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) p[i][j] = a[j][i].x;
    for (int i = 0; i < 3; i++) sort(a[i], a[i] + n), M[i].clear();
    for (int i = 0; i < 3; i++)
    {
      int block = 0;
      for (int j = 0; j <= n / sqn; j++) ans[i][j].reset();
      for (int j = 0; j < n; j++)
      {
        if (j / sqn == block + 1) ans[i][j / sqn]|= ans[i][block++];
        ans[i][j / sqn][a[i][j].id] = 1;
        M[i][a[i][j].x] = j;
      }
    }
    for (int i = 0; i < n; i++)
    {
      for (int j = 0, block, now; j < 3; j++)
      {
        now = M[j][p[i][j]];  res[j].reset(); 
        if (block = now / sqn) res[j] |= ans[j][block - 1];
        for (int k = now; k / sqn == block&&k >= 0; k--) res[j][a[j][k].id] = 1;
      }
      printf("%d\n", (res[0] & res[1] & res[2]).count() - 1);
    }
  }
  return 0;
}

排序+線段樹套treap，常數比較大

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
int T, n, ans[maxn];

struct point
{
  int x, y, z, id;
  void read(int d){ scanf("%d%d%d", &x, &y, &z); id = d; }
  bool operator<(const point& a) const
  {
    return x == a.x ? y == a.y ? z < a.z : y < a.y : x < a.x;
  }
  bool operator==(const point& a) const
  {
    return x == a.x&&y == a.y&&z == a.z;
  }
}a[maxn];


struct Node
{
  int v, p, cnt, inc;
  Node *l, *r;
  Node(int v = 0, int p = 0) :v(v), p(p){ l = r = NULL; cnt = inc = 1; }
  void clear(){ if (l) l->clear(); if (r) r->clear(); delete[]this; }
};

struct Treap
{
#define node Node*
#define now (*root)
  Node *root;
  void Count(node root)
  {
    root->cnt = root->inc;
    if (root->l) root->cnt += root->l->cnt;
    if (root->r) root->cnt += root->r->cnt;
  }
  void rotate_left(node *root)
  {
    node right = now->r;
    now->r = right->l;
    right->l = now;
    now = right;
    Count(now->l); Count(now);
  }
  void rotate_right(node *root)
  {
    node left = now->l;
    now->l = left->r;
    left->r = now;
    now = left;
    Count(now->r); Count(now);
  }
  void Insert(node *root, int v, int p)
  {
    if (!now) { now = new Node(v, p); return; }
    if (now->v == v) now->inc++;
    else if (v < now->v)
    {
      Insert(&(now->l), v, p);
      if (now->l->p < now->p) rotate_right(root);
    }
    else
    {
      Insert(&(now->r), v, p);
      if (now->r->p < now->p) rotate_left(root);
    }
    Count(now);
  }
  void add(int x){ Insert(&root, x, rand() % mod); }
  void Delete(node *root, int v)
  {
    if (!now) return;
    if (v < now->v) Delete(&(now->l), v);
    if (v > now->v) Delete(&(now->r), v);
    if (v == now->v)
    {
      if (now->inc > 1) now->inc--;
      else if (!now->l || !now->r)
      {
        node temp = now;
        if (now->l) now = now->l; else now = now->r;
        delete[] temp; return;
      }
      else
      {
        if (now->l->p < now->r->p)
        {
          rotate_right(root);
          Delete(&(now->r), v);
        }
        else
        {
          rotate_left(root);
          Delete(&(now->l), v);
        }
      }
    }
    Count(now);
  }
  void dec(int x){ Delete(&root, x); }
  int find(int x)
  {
    int ans = 0;
    for (node temp = root; temp;)
    {
      int left = temp->l ? temp->l->cnt : 0;
      if (x < temp->v) temp = temp->l;
      else
      {
        ans += left + temp->inc;
        if (x == temp->v) return ans;
        temp = temp->r;
      }
    }
    return ans;
  }
  void clear(){ if (root) root->clear(); root = NULL; }
};

struct Tree
{
  Treap f[maxn * 4];
  void insert(int x, int l, int r, int u, int v)
  {
    f[x].add(v);
    if (l == r) return; 
    int mid = l + r >> 1;
    if (u <= mid) insert(x << 1, l, mid, u, v);
    else insert(x << 1 | 1, mid + 1, r, u, v);
  }
  int get(int x, int l, int r, int u, int v)
  {
    if (r <= u) return f[x].find(v);
    int mid = l + r >> 1;
    if (u <= mid) return get(x << 1, l, mid, u, v);
    else return get(x << 1, l, mid, u, v) + get(x << 1 | 1, mid + 1, r, u, v);
  }
  void release(int x, int l, int r)
  {
    f[x].clear();
    if (l == r) return;
    int mid = l + r >> 1;
    release(x << 1, l, mid);
    release(x << 1 | 1, mid + 1, r);
  }
}st;


int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    int maxy = 0;
    for (int i = 0; i < n; i++)
    {
      a[i].read(i);
      maxy = max(maxy, a[i].y);
      ans[i] = 0;
    }
    sort(a, a + n);
    for (int i = n - 2; i >= 0; i--)
      if (a[i] == a[i + 1]) ans[a[i].id] = ans[a[i + 1].id] + 1;
    st.release(1, 1, maxy);
    for (int i = 0; i < n; i++)
    {
      ans[a[i].id] += st.get(1, 1, maxy, a[i].y, a[i].z);
      st.insert(1, 1, maxy, a[i].y, a[i].z);
    }
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  }
  return 0;
}

排序+樹狀數組套treap

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
typedef long long LL;
const int low(int x){ return x&-x; }
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int T, n, ans[maxn], maxy;

struct point
{
  int x, y, z, id;
  void read(int d){ scanf("%d%d%d", &x, &y, &z); id = d; }
  bool operator<(const point& a) const
  {
    return x == a.x ? y == a.y ? z < a.z : y < a.y : x < a.x;
  }
  bool operator==(const point& a) const
  {
    return x == a.x&&y == a.y&&z == a.z;
  }
}a[maxn];

struct Node
{
  int v, p, cnt, inc;
  Node *l, *r;
  Node(int v = 0, int p = 0) :v(v), p(p){ l = r = NULL; cnt = inc = 1; }
  void clear(){ if (l) l->clear(); if (r) r->clear(); delete[]this; }
};

struct Treap
{
#define node Node*
#define now (*root)
  Node *root;
  void Count(node root)
  {
    root->cnt = root->inc;
    if (root->l) root->cnt += root->l->cnt;
    if (root->r) root->cnt += root->r->cnt;
  }
  void rotate_left(node *root)
  {
    node right = now->r;
    now->r = right->l;
    right->l = now;
    now = right;
    Count(now->l); Count(now);
  }
  void rotate_right(node *root)
  {
    node left = now->l;
    now->l = left->r;
    left->r = now;
    now = left;
    Count(now->r); Count(now);
  }
  void Insert(node *root, int v, int p)
  {
    if (!now) { now = new Node(v, p); return; }
    if (now->v == v) now->inc++;
    else if (v < now->v)
    {
      Insert(&(now->l), v, p);
      if (now->l->p < now->p) rotate_right(root);
    }
    else
    {
      Insert(&(now->r), v, p);
      if (now->r->p < now->p) rotate_left(root);
    }
    Count(now);
  }
  void add(int x){ Insert(&root, x, rand() % mod); }
  void Delete(node *root, int v)
  {
    if (!now) return;
    if (v < now->v) Delete(&(now->l), v);
    if (v > now->v) Delete(&(now->r), v);
    if (v == now->v)
    {
      if (now->inc > 1) now->inc--;
      else if (!now->l || !now->r)
      {
        node temp = now;
        if (now->l) now = now->l; else now = now->r;
        delete[] temp; return;
      }
      else
      {
        if (now->l->p < now->r->p)
        {
          rotate_right(root);
          Delete(&(now->r), v);
        }
        else
        {
          rotate_left(root);
          Delete(&(now->l), v);
        }
      }
    }
    Count(now);
  }
  void dec(int x){ Delete(&root, x); }
  int find(int x)
  {
    int ans = 0;
    for (node temp = root; temp;)
    {
      int left = temp->l ? temp->l->cnt : 0;
      if (x < temp->v) temp = temp->l;
      else
      {
        ans += left + temp->inc;
        if (x == temp->v) return ans;
        temp = temp->r;
      }
    }
    return ans;
  }
  void clear(){ if (root) root->clear(); root = NULL; }
};

Treap f[maxn];

void insert(int x, int y)
{
  for (int i = x; i <= maxy; i += low(i)) f[i].add(y);
}

int get(int x, int y)
{
  int ans = 0;
  for (int i = x; i; i -= low(i)) ans += f[i].find(y);
  return ans;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    maxy = 0;
    for (int i = 0; i < n; i++) a[i].read(i), maxy = max(maxy, a[i].y), ans[i] = 0;
    sort(a, a + n);
    for (int i = 1; i <= maxy; i++) f[i].clear();
    for (int i = n - 2; i >= 0; i--)
      if (a[i] == a[i + 1]) ans[a[i].id] = ans[a[i + 1].id] + 1;
    for (int i = 0; i < n; i++)
    {
      ans[a[i].id] += get(a[i].y, a[i].z);
      insert(a[i].y, a[i].z);
    }
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  }
  return 0;
}

排序+樹狀數組套treap，用數組寫的比指針要快點，不需要去釋放空間

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
typedef long long LL;
const int low(int x){ return x&-x; }
const int maxn = 1e5 + 10;
int T, n, ans[maxn], maxy, f[maxn];

struct point
{
  int x, y, z, id;
  void read(int d){ scanf("%d%d%d", &x, &y, &z); id = d; }
  bool operator<(const point& a) const
  {
    return x == a.x ? y == a.y ? z < a.z : y < a.y : x < a.x;
  }
  bool operator==(const point& a) const
  {
    return x == a.x&&y == a.y&&z == a.z;
  }
}a[maxn];

struct Treaps
{
  const static int maxn = 1e6 + 5e5;
  const static int mod = 1e9 + 7;
  int L[maxn], R[maxn], v[maxn], p[maxn], A[maxn], C[maxn], tot;
  void clear(){ L[0] = R[0] = C[0] = 0; tot = 1; }
  int Node(int V, int P){ L[tot] = R[tot] = 0; v[tot] = V; p[tot] = P; A[tot] = C[tot] = 1; return tot++; }
  int NewTree(int x){ return Node(x, rand() % mod); }
  void Count(int x){ C[x] = A[x] + C[L[x]] + C[R[x]]; }
  void rotate_right(int &x)
  {
    int y = L[x]; L[x] = R[y]; R[y] = x; x = y; Count(R[x]);
  }
  void rotate_left(int &x)
  {
    int y = R[x]; R[x] = L[y]; L[y] = x; x = y; Count(L[x]);
  }
  void Insert(int& x, int V, int P)
  {
    if (!x) { x = Node(V, P); return; }
    if (v[x] == V) ++A[x];
    else if (V < v[x])
    {
      Insert(L[x], V, P);
      if (p[x]>p[L[x]]) rotate_right(x);
    }
    else 
    {
      Insert(R[x], V, P);
      if (p[x] > p[R[x]]) rotate_left(x);
    }
    Count(x);
  }
  void add(int &x, int V){ Insert(x, V, rand() % mod); }
  void Delete(int &x, int V)
  {
    if (!x) return;
    if (V < v[x]) Delete(L[x], V);
    else if (V > v[x]) Delete(R[x], V);
    else
    {
      if (A[x] > 1) --A[x];
      else if (!L[x] || !R[x]) x = L[x] ? L[x] : R[x];
      else
      {
        if (p[L[x]] < p[R[x]])
        {
          rotate_right(x);
          Delete(R[x], V);
        }
        else
        {
          rotate_left(x);
          Delete(L[x], V);
        }
      }
    }
    Count(x);
  }
  void dec(int &x, int V) { Delete(x, V); }
  int find(int x, int V)
  {
    int ans = 0;
    for (int i = x; i;)
    {
      if (V < v[i]) i = L[i];
      else
      {
        ans += C[L[i]] + A[i];
        if (V == v[i]) break;
        i = R[i];
      }
    }
    return ans;
  }
}t;

void insert(int x, int y)
{
  for (int i = x; i <= maxy; i += low(i)) if (f[i]) t.add(f[i], y); else f[i] = t.NewTree(y);
}

int get(int x, int y)
{
  int ans = 0;
  for (int i = x; i; i -= low(i)) ans+=t.find(f[i], y);
  return ans;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    maxy = 0;
    t.clear();
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; i++) a[i].read(i), maxy = max(maxy, a[i].y), ans[i] = 0;
    sort(a, a + n);
    for (int i = n - 2; i >= 0; i--)
    if (a[i] == a[i + 1]) ans[a[i].id] = ans[a[i + 1].id] + 1;
    for (int i = 0; i < n; i++)
    {
      ans[a[i].id] += get(a[i].y, a[i].z);
      insert(a[i].y, a[i].z);
    }
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  }
  return 0;
}

HDU 5618 Jam's problem again

繼續閱讀

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)

HDU5066-Harry And Physical Teacher Harry And Physical Teacher