【BZOJ 3262】あぜ道に花が咲く(CDQ分治+樹状配列)
3262:あぜ道に花が咲く
Time Limit: 20 Sec
Memory Limit: 256 MB
Submit: 1424
Solved: 641
[ Submit][ Status][ Discuss]
Description
n個の花があり、各花には3つの属性がある:花形(s)、色(c)、におい(m)、また3つの整数で表される.それぞれの花を評価するには、1つの花のレベルは、その美しさが超える花の数です.一方の花Aが他方の花Bよりも美しいと定義され、Sa>=Sb、Ca>=Cb、Ma>=Mbのみである.明らかに、2つの花には同じ属性がある可能性があります.各等級を評価する花の数を統計する必要がある.
Input
第1の挙動N,K(1<=N<=100000,1<=K<=200000)は、それぞれ花の数と最大属性値を表す.
以下のN行は、1行あたり3つの整数si,ci,mi(1<=si,ci,mi<=K)であり、i番目の花の属性を表す
Output
評価が0であることを示すN行を含む...N-1の各段の花の数.
Sample Input
10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1
Sample Output
3 1 3 0 1 0 1 0 0 1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
Source
ツリーカバーCDQ分治
[ Submit][ Status][ Discuss]
【問題解】【CDQ分治】
【このアルゴリズムは一般的に非強制オンライン問題しか解決できない.分治に属する以上、その思想も必然的に分治、すなわち二分操作である.一般的には、木で操作の区間を維持することによって答えを探す】
【我々は[l,r]を現在処理すべき区間とすると、[l,mid]を再帰的に処理し、[l,mid]の操作数毎に[mid+1,r]区間の操作に及ぼす影響を列挙処理し、[mid+1,r]区間を再帰的に処理する】
【本題では、各操作には3次元が含まれており、まず1次元キーで並べ替え、重さを除いて、配列に同じ花が何本あるかを記録します.その後、CDQ分治処理、処理時に、[l,mid]区間と[mid+1,r]区間をそれぞれ2次元キーで並べ替え、木状配列で3次元を下にして、各花の出現回数を維持します.[l,mid]が[mid+1,r]に及ぼす影響を処理するたびに、2次元目の影響を考慮するだけでよい([l,mid]区間のxは必ず[mid+1,r]区間のxより小さく、3次元目用ツリー配列のメンテナンスも考慮する必要がないため)、2次元目が要求に合致した場合、その影響をツリー配列に加える.[mid+1,r]区間の1つの操作が検索されるたびに、答えを更新する]
Time Limit: 20 Sec
Memory Limit: 256 MB
Submit: 1424
Solved: 641
[ Submit][ Status][ Discuss]
Description
n個の花があり、各花には3つの属性がある:花形(s)、色(c)、におい(m)、また3つの整数で表される.それぞれの花を評価するには、1つの花のレベルは、その美しさが超える花の数です.一方の花Aが他方の花Bよりも美しいと定義され、Sa>=Sb、Ca>=Cb、Ma>=Mbのみである.明らかに、2つの花には同じ属性がある可能性があります.各等級を評価する花の数を統計する必要がある.
Input
第1の挙動N,K(1<=N<=100000,1<=K<=200000)は、それぞれ花の数と最大属性値を表す.
以下のN行は、1行あたり3つの整数si,ci,mi(1<=si,ci,mi<=K)であり、i番目の花の属性を表す
Output
評価が0であることを示すN行を含む...N-1の各段の花の数.
Sample Input
10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1
Sample Output
3 1 3 0 1 0 1 0 0 1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
Source
ツリーカバーCDQ分治
[ Submit][ Status][ Discuss]
【問題解】【CDQ分治】
【このアルゴリズムは一般的に非強制オンライン問題しか解決できない.分治に属する以上、その思想も必然的に分治、すなわち二分操作である.一般的には、木で操作の区間を維持することによって答えを探す】
【我々は[l,r]を現在処理すべき区間とすると、[l,mid]を再帰的に処理し、[l,mid]の操作数毎に[mid+1,r]区間の操作に及ぼす影響を列挙処理し、[mid+1,r]区間を再帰的に処理する】
【本題では、各操作には3次元が含まれており、まず1次元キーで並べ替え、重さを除いて、配列に同じ花が何本あるかを記録します.その後、CDQ分治処理、処理時に、[l,mid]区間と[mid+1,r]区間をそれぞれ2次元キーで並べ替え、木状配列で3次元を下にして、各花の出現回数を維持します.[l,mid]が[mid+1,r]に及ぼす影響を処理するたびに、2次元目の影響を考慮するだけでよい([l,mid]区間のxは必ず[mid+1,r]区間のxより小さく、3次元目用ツリー配列のメンテナンスも考慮する必要がないため)、2次元目が要求に合致した場合、その影響をツリー配列に加える.[mid+1,r]区間の1つの操作が検索されるたびに、答えを更新する]
#include
#include
#include
using namespace std;
struct flower{
int x,y,z;
int cnt,ans;
}d[1000010];
int tree[3000010],n,k,tot,num[1000010];
int tmp(flower a,flower b)
{
if(a.xb.x) return 0;
if(a.yb.y) return 0;
if(a.zb.y) return 0;
if(a.zb.z) return 0;
if(a.x>1;
CDQ(l,mid); CDQ(mid+1,r);
sort(d+l,d+mid+1,cmp);
sort(d+mid+1,d+r+1,cmp);
int j=l;
for(int i=mid+1;i<=r;++i)
{
while(j<=mid&&d[j].y<=d[i].y)
updata(d[j].z,d[j].cnt),++j;
d[i].ans+=ask(d[i].z);
}
for(int i=l;i