Chlience

【题解】BZOJ 3262 陌上花开
Probelm传送门 >ω<题目大意:每朵花是一个三元组 $a_i , b_i , c_i$设当 $a_j \le...
扫描右侧二维码阅读全文
15
2018/10

【题解】BZOJ 3262 陌上花开

Probelm

传送门 >ω<

题目大意:

每朵花是一个三元组 $a_i , b_i , c_i$

设当 $a_j \leq a_i \ \&\&\ b_j \leq b_i \ \&\&\ c_j \leq c_i$ 则称 $i$ 比 $j$ 优

问每朵花比多少花优?

Solution

三维偏序模板

容易看出,第一维排序,第二维分治,第三维树状数组即可解决问题

但是为什么 WA 呢?
因为 CDQ分治 比较兹磁严格不等问题,而非严格不等就需要一些操作将其变为严格不等

那么这道题在 $a$ 排序需要考虑 $b , c$ ,并且合并相同点,同时保证在分治时先修改再询问,这样就能转化为严格不等,进而解决这道题

记得最后相同点的贡献也要计算啊qwq

代码

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int M = 200010; 
#define mid ((l + r) >> 1)
int n;
struct flower {int a , b , c , u , v;}f[N] , t[N];

bool cmp(flower a , flower b) {
    if(a.a == b.a)
        if(a.b == b.b) return a.c < b.c;
        else return a.b < b.b;
    else return a.a < b.a;
}

int a[M] , ans[N];
int lowbit(int x) {return x & (-x);}
void add(int x , int y) {for(; x <= 200000 ; x += lowbit(x)) a[x] += y;}
int query(int x) {int ans = 0; for(; x ; x -= lowbit(x)) ans += a[x]; return ans;}

void cdq(int l , int r) {
    if(l == r) return;
    cdq(l , mid); cdq(mid + 1 , r);
    int i = l , j = mid + 1 , p = l;
    while(i <= mid || j <= r) {
        if(j > r || (i <= mid && f[i].b <= f[j].b)) {
            add(f[i].c , f[i].u);
            t[p ++] = f[i ++];
        }
        else {
            f[j].v += query(f[j].c);
            t[p ++] = f[j ++];
        }
    }
    for(i = l ; i <= mid ; ++ i) add(f[i].c , - f[i].u);
    for(i = l ; i <= r ; ++ i) f[i] = t[i];
}

int main() {
    n = read(); read();
    for(int i = 1 ; i <= n ; ++ i) {
        f[i].a = read();
        f[i].b = read();
        f[i].c = read();
        f[i].u = 1;
    }
    sort(f + 1 , f + n + 1 , cmp);
    
    int p = 1;
    for(int i = 2 ; i <= n ; ++ i)
        if(f[i].a == f[p].a && f[i].b == f[p].b && f[i].c == f[p].c) ++ f[p].u;
        else f[++ p] = f[i];

    cdq(1 , p);
    
    for(int i = 1 ; i <= p ; ++ i) ans[f[i].u + f[i].v - 1] += f[i].u;
    for(int i = 0 ; i < n ; ++ i)
        printf("%d\n" , ans[i]);
    return 0;
}
Last modification:October 15th, 2018 at 06:18 pm

Leave a Comment