生活随笔
收集整理的這篇文章主要介紹了
BZOJ3262/Luogu3810 陌上花开 (三维偏序,CDQ)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
一個下午的光陰之死，兇手是細節(jié)與手殘。
致命的一槍：BIT存權(quán)值時:
for(; x <= maxx; x += x&-x) t[x] += w;//for(; x <= n; x += x&-x) t[x] += w;// You died int n;
int maxx;struct Element{int a,b,c;long long ans;int siz;bool operator< (const Element &com)const{if(a != com.a) return a < com.a;if(b != com.b) return b < com.b;return c < com.c;}
}a[N],tmp[N];long long t[N];
inline void Updata(int x, int w){for(; x <= maxx; x += x&-x) t[x] += w;//for(; x <= n; x += x&-x) t[x] += w;// You died
}
inline long long Query(int x){long long s = 0;for(; x; x -= x&-x) s += t[x];return s;
}inline void CDQ(int l,int r){if(l == r){a[l].ans += a[l].siz - 1;return;}int mid = (l + r) >> 1;CDQ(l, mid), CDQ(mid + 1, r);int i = l, j = mid + 1, k = l;while(i <= mid && j <= r){if(a[i].b <= a[j].b){Updata(a[i].c, a[i].siz);tmp[k++] = a[i++];}else{a[j].ans += Query(a[j].c);tmp[k++] = a[j++];}}while(j <= r) a[j].ans += Query(a[j].c), tmp[k++] = a[j++];R(j, l, i - 1) Updata(a[j].c, -a[j].siz);while(i <= mid) tmp[k++] = a[i++];R(i,l,r) a[i] = tmp[i];
}long long tot[N];
int main(){
// freopen("In.txt","r",stdin);
// freopen("OUT.txt","w",stdout);io >> n >> maxx;R(i,1,n){io >> a[i].a >> a[i].b >> a[i].c;}sort(a + 1, a + n + 1);int cnt = 0;R(i,1,n){if(a[i].a == a[i-1].a && a[i].b == a[i-1].b && a[i].c == a[i-1].c && i != 1){++a[cnt].siz;}else{a[++cnt] = a[i];a[cnt].siz = 1;}}CDQ(1, cnt);R(i,1,cnt){tot[a[i].ans] += a[i].siz;}--n;R(i,0,n){printf("%lld\n", tot[i]);}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/bingoyes/p/11181554.html
總結(jié)
以上是生活随笔為你收集整理的BZOJ3262/Luogu3810 陌上花开 (三维偏序,CDQ)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
