Tsinsen-1487:分配游戏【树状数组】

　　首先一定要看到x + y + z = N这个条件，没看到就世界再见了。

　　赢的人得分需要大于等于2，那么无非就是 (x, y), (x, z), (y, z), (x, y, z) 大于其他的点。但是考虑一下(x, y, z)均大于是不可能的，因为 x + y + z = N。(x, y) 和 (x, z) 这样的也不可能同时大于一个点，那么符合条件的点，只能满足(x, y), (x, z), (y, z)其中之一，所以我们把每一个点拆分为3个点，分别投影到xOy, xOz, yOz平面上，然后需要处理的就是在一个二维平面内的指定点有多少个小于它了。

　　二位树状数组肯定是可以的，但是空间需要为 n^2 ，无疑不可行，那么我们考虑固定一维，把查询和插入操作混在一起，给查询操作和插入操作标号，因为在同一个横坐标出，查询操作优先，所以我们把查询操作标号为0，插入操作标号为1。这样打包make_pair(x, op, y, self_id)，直接使用pair的运算符即可。

 #include <bits/stdc++.h>

 #define rep(i, a, b) for (int i = a; i <= b; i++)

 #define REP(i, a, b) for (int i = a; i < b; i++)

 #define drep(i, a, b) for (int i = a; i >= b; i--)

 #define travel(x) for (int i = G[x]; i; i = E[i].nx)

 #define mp make_pair

 #define pb push_back

 #define clr(x) memset(x, 0, sizeof(x))

 #define xx first

 #define yy second

 using namespace std;

 typedef long long i64;

 typedef pair<int, int> pii;

 //********************************

 const int maxn = ;

 pair<int, pair<int, int> > sa[maxn];

 pair<int, pair<int, int> > st[maxn];

 pair<int, pair<int, pair<int, int> > > query[maxn << ];

 int top;

 int hsh[(maxn << ) * ], cd;

 int ans[maxn];

 int c[(maxn << ) * ];

 void Insrt(int x, int v) {

     while (x <= cd) {

         c[x] += v;

         x += x & -x;

     }

 }

 int Query(int x) {

     int ret();

     while (x > ) {

         ret += c[x];

         x -= x & -x;

     }

     return ret;

 }

 int read() {

     int l = , s(); char ch = getchar();

     while (ch < '' || ch > '') { if (ch == '-') l = -; ch = getchar(); }

     while (ch >= '' && ch <= '') { s = (s << ) + (s << ) + ch - ''; ch = getchar(); }

     return l * s;

 }

 int main() {

     int N, m, T; N = read(), m = read(), T = read();

     rep(i, , m) sa[i].xx = read(), sa[i].yy.xx = read(), sa[i].yy.yy = read(), hsh[++cd] = sa[i].xx, hsh[++cd] = sa[i].yy.xx, hsh[++cd] = sa[i].yy.yy;

     rep(i, , T) st[i].xx = read(), st[i].yy.xx = read(), st[i].yy.yy = read(), hsh[++cd] = st[i].xx, hsh[++cd] = st[i].yy.xx, hsh[++cd] = st[i].yy.yy;

     sort(hsh + , hsh +  + cd); cd = unique(hsh + , hsh +  + cd) - (hsh + );

     rep(i, , m) {

         sa[i].xx = lower_bound(hsh + , hsh +  + cd, sa[i].xx) - hsh;

         sa[i].yy.xx = lower_bound(hsh + , hsh +  + cd, sa[i].yy.xx) - hsh;

         sa[i].yy.yy = lower_bound(hsh + , hsh +  + cd, sa[i].yy.yy) - hsh;

     }

     rep(i, , T) {

         st[i].xx = lower_bound(hsh + , hsh +  + cd, st[i].xx) - hsh;

         st[i].yy.xx = lower_bound(hsh + , hsh +  + cd, st[i].yy.xx) - hsh;

         st[i].yy.yy = lower_bound(hsh + , hsh +  + cd, st[i].yy.yy) - hsh;

     }

     rep(i, , m) query[++top] = mp(sa[i].xx, mp(, mp(sa[i].yy.xx, i)));

     rep(i, , T) query[++top] = mp(st[i].xx, mp(, mp(st[i].yy.xx, i)));

     sort(query + , query +  + top);

     rep(i, , top) {

         if (query[i].yy.xx == ) ans[query[i].yy.yy.yy] += Query(query[i].yy.yy.xx - );

         else Insrt(query[i].yy.yy.xx, );

     }

     memset(c, , sizeof(c)); top = ;

     rep(i, , m) query[++top] = mp(sa[i].xx, mp(, mp(sa[i].yy.yy, i)));

     rep(i, , T) query[++top] = mp(st[i].xx, mp(, mp(st[i].yy.yy, i)));

     sort(query + , query +  + top);

     rep(i, , top) {

         if (query[i].yy.xx == ) ans[query[i].yy.yy.yy] += Query(query[i].yy.yy.xx - );

         else Insrt(query[i].yy.yy.xx, );

     }

     memset(c, , sizeof(c)); top = ;

     rep(i, , m) query[++top] = mp(sa[i].yy.xx, mp(, mp(sa[i].yy.yy, i)));

     rep(i, , T) query[++top] = mp(st[i].yy.xx, mp(, mp(st[i].yy.yy, i)));

     sort(query + , query +  + top);

     rep(i, , top) {

         if (query[i].yy.xx == ) ans[query[i].yy.yy.yy] += Query(query[i].yy.yy.xx - );

         else Insrt(query[i].yy.yy.xx, );

     }

     rep(i, , T) printf("%d\n", ans[i]);

     return ;

 }

巴特西

Tsinsen-1487:分配游戏【树状数组】

最新文章

热门文章