BZOJ3262: 陌上花開
題意概述
有N朵花,對于每一朵花,有三個屬性:s,c,m. 當且僅當si>sj,ci>cj,mi>mj,有花i比花j美麗. 一朵花的評級為比其他花更美麗的數量(不包括自己),輸出評級為0 N?1的花的數量.
題目分析:
初學CDQ分治,寫了一下午.orz……
這是一個三維偏序的問題,可以用CDQ來搞一搞. 當然此題當中,一朵花既是修改操作,又是詢問操作. 先以一維s從小到大排序,開始CDQ分治. 對于每一次完成兩個子問題后,合并時,先按照c從小到大排序,第三維m用樹狀數組維護,對于當前花,若是左區間的花,樹狀數組add操作,否則,查詢m比其小的花的個數.
(千萬要注意三個屬性均相同的花的處理,一種方法是先去重,再計算)
代碼:
//Continue#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int maxn=100000+10;int read() { char ch=getchar();int ret=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar(); return ret;}struct Flower { int s,c,m,k,cnt,ans;//k:0 add操作,1 sum操作 //cnt記錄這種花有多少,ans指的是這種花的評級 Flower(int cnt=0,int ans=0){} bool Operator < (const Flower& rhs) const { return c<rhs.c||(c==rhs.c&&(m<rhs.m||(m==rhs.m&&s<rhs.s))); } bool operator == (const Flower& rhs) const { return s==rhs.s&&c==rhs.c&&m==rhs.m; } void input() { s=read();c=read();m=read(); }}t[maxn],f[maxn];#define lowbit(x) (x&-x)int bit[maxn],N,K;void add(int d,int v) { for(;d<=K;d+=lowbit(d)) bit[d]+=v;}int sum(int d,int ret=0) { for(;d;d-=lowbit(d)) ret+=bit[d]; return ret;}#define mid ((l+r)>>1)int cmp(const Flower& a,const Flower& b) { return a.s<b.s||(a.s==b.s&&(a.c<b.c||(a.c==b.c&&a.m<b.m)));}void solve(int l,int r) { if(l==r) return ; //先遞歸解決左右子區間內部更新 solve(l,mid); solve(mid+1,r); //此時解決左右區間間的更新 for(int i=l;i<=mid;i++) f[i].k=0;//左區間修改 for(int i=mid+1;i<=r;i++) f[i].k=1;//右區間查詢 sort(f+l,f+r+1);//按照c排序 for(int i=l;i<=r;i++) if(f[i].k) f[i].ans+=sum(f[i].m);//右區間查詢 else add(f[i].m,f[i].cnt);//左區間修改 //注意在用分治求解的時候不能引入序列長度的時間復雜度,否則會造成時間復雜度退化 for(int i=l;i<=r;i++) if(!f[i].k) add(f[i].m,-f[i].cnt);//采用倒著修改回去的方法 }int ans[maxn],tot;int main() { N=read();K=read(); for(int i=1;i<=N;i++) t[i].input(); sort(t+1,t+N+1,cmp); for(int i=1;i<=N;i++)//先去重操作 if(i==1||!(t[i]==t[i-1])) f[++tot]=t[i],f[tot].cnt=1; else ++f[tot].cnt; for(int i=1;i<=tot;i++) f[i].ans=f[i].cnt-1;//一開始評級賦值為個數-1 sort(f+1,f+tot+1,cmp);//按s排序 solve(1,tot); for(int i=1;i<=tot;i++) ans[f[i].ans]+=f[i].cnt; for(int i=0;i<N;i++)
