CDQ分治入門---バッタ災害、Mokia
18145 ワード
标题:W*W(W<=500000)の行列、初期はすべて0で、N(N<=200000)個の問い合わせ、単点に1つの値を加えて、区間クエリーと.分析:この問題はデータ構造を見ると、2次元線分樹は明らかにだめだが、水30分でいい.
もちろん、私たちは30点に満足できないので、正解CDQ分治...solve(l,r)を定義します:すべての修正操作∈(l,mid)を探して、区間(mid+1,r)のクエリー操作に対する影響を計算して、それから絶えず分治します.この問題については,分治のたびに区間内の操作をx軸で並べ替え,1次元のツリー配列で操作状態を計算し,クエリー操作を直接計算すればよい.
最初のCDQ分治はこのように解决しました!!!そしてCOGSには1752という似たような問題があることに気づいた.[BOI 2007]摩基亜Mokiaそれから私はこの2つの问题が同じだと思って、そこでデータの范囲を変えて交际して、それから、私は成功したMLE...MLE......そして私は私のプログラムの弊害を発見しました.それは、分治操作のたびに、cc[]を別の配列にしましたが、実は必要ありません.私は本当に直すのがおっくうです.だから、ここのOrz Mikumikumi先輩は...
それからまだ终わっていません...私は[IOI 2001]携帯电话がこの2つの问题と同じように见えることを発见します...このTMは本当にIOIですか?こんなに水...それから私はまた新しい発见があります...この问题のデータの范囲はまるで小さいです..これは直接に2次元の木の形の配列ですることができます...その上暴力も过ごすことができるようです...私はコードを贴らないで...问题あなた达も自分で探します~
#includefor(int j=y;jint gsum(int x,int y){
int ans=0;
for(int i=x;i;i-=lowbit(i)){
for(int j=y;j;j-=lowbit(j)){
ans+=c[i][j];
}
}
return ans;
}
int query(int x1,int y1,int x2,int y2){
return gsum(x2,y2)+gsum(x1-1,y1-1)-gsum(x2,y1-1)-gsum(x1-1,y2);
}
int main(){
freopen("locust.in","r",stdin);
freopen("locust.out","w",stdout);
int w,n;
scanf("%d %d",&w,&n);
int flag,a,b,c,d;
while(n--){
scanf("%d",&flag);
if(flag==1){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}else{
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d
",query(a,b,c,d));
}
}
return 0;
}
もちろん、私たちは30点に満足できないので、正解CDQ分治...solve(l,r)を定義します:すべての修正操作∈(l,mid)を探して、区間(mid+1,r)のクエリー操作に対する影響を計算して、それから絶えず分治します.この問題については,分治のたびに区間内の操作をx軸で並べ替え,1次元のツリー配列で操作状態を計算し,クエリー操作を直接計算すればよい.
#includereturn a.x1void solve(int l,int r){ //CDQ
if(l==r) return;
int mid=(l+r)>>1;
//printf("%d%d
",l,r);
int cnt=0;
for(int i=l;i<=mid;i++){ // (l,mid)
if(p[i].op==1)
cc[cnt++]=p[i];
}
for(int i=mid+1;i<=r;i++){ // (mid+1,r)
if(p[i].op==2){
cc[cnt++]=p[i];
cc[cnt++]=p[i];
cc[cnt-2].x1--; // x2 x1-1 (x1,x2)
cc[cnt-1].x1=p[i].x2;
cc[cnt-1].op=3;
}
}
sort(cc,cc+cnt,cmp); // x
for(int i=0;iif(cc[i].op==1){
add(cc[i].y1,cc[i].k); //
}
else if(cc[i].op==2){
p[cc[i].num].ans -= sum(cc[i].y2)-sum(cc[i].y1-1); // x1-1
}
else {
p[cc[i].num].ans += sum(cc[i].y2)-sum(cc[i].y1-1); // x2
}
}
for(int i=0;iif(cc[i].op==1){
add(cc[i].y1,-cc[i].k); // c
}
}
solve(l,mid);
solve(mid+1,r); //
return ;
}
int MAIN(){
freopen("locust.in","r",stdin);
freopen("locust.out","w",stdout);
scanf("%d %d",&w,&n);
int flag,a,b,c,d;
for(int i=1;i<=n;i++){
//scanf("%d",&flag);
flag=in();
if(flag==1){
//scanf("%d%d%d",&a,&b,&c);
a=in();b=in();c=in();
p[i].op=1;
p[i].x1=a;
p[i].y1=b;
p[i].k=c;
}else{
//scanf("%d%d%d%d",&a,&b,&c,&d);
a=in();b=in();c=in();d=in();
p[i].op=2;
p[i].x1=min(a,c);
p[i].y1=min(b,d);
p[i].x2=max(a,c);
p[i].y2=max(b,d);
}
p[i].num=i;
}
solve(1,n);
for(int i=1;i<=n;i++){
if(p[i].op==2) printf("%d
",p[i].ans);
}
return 0;
}
int main(){;}
int helenkeller=MAIN(); 最初のCDQ分治はこのように解决しました!!!そしてCOGSには1752という似たような問題があることに気づいた.[BOI 2007]摩基亜Mokiaそれから私はこの2つの问题が同じだと思って、そこでデータの范囲を変えて交际して、それから、私は成功したMLE...MLE......そして私は私のプログラムの弊害を発見しました.それは、分治操作のたびに、cc[]を別の配列にしましたが、実は必要ありません.私は本当に直すのがおっくうです.だから、ここのOrz Mikumikumi先輩は...
#include2000010];
int lowbit(int x)
{
return x&-x;
}
int query(int x)
{
int re=0;
while(x>0){re+=Bit[x];x-=lowbit(x);}
return re;
}
void add(int x,int y)
{
while(x<=n){Bit[x]+=y;x+=lowbit(x);}
}
void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
sort(Q+l,Q+mid+1);sort(Q+mid+1,Q+r+1);
int L=l,inq=0;
for(int i=mid+1;i<=r;i++)
{
if(Q[i].k==2)
{
while(L<=mid&&Q[L].x<=Q[i].x)
{
if(Q[L].k==1)
{
add(Q[L].y,Q[L].s);
H[++inq]=L;
}
L++;
}
ans[Q[i].q]+=Q[i].s*query(Q[i].y);
}
//cout<
}
for(int i=1;i<=inq;i++)
add(Q[H[i]].y,-Q[H[i]].s);
}
void push(int x,int y,int k,int v,int t)
{
if(x>0&&y>0)
Q[++tot]=miku(x,y,k,v,t);
}
int main()
{
freopen("mokia.in","r",stdin);
freopen("mokia.out","w",stdout);
int x1,y1,x2,y2,v,tail=0;
while(scanf("%d",&cmd)&&cmd!=3)
{
if(cmd==0)
{
scanf("%d",&n);
}
if(cmd==1)
{
scanf("%d%d%d",&x1,&x2,&v);
push(x1,x2,1,v,0);
//printf("1");
}
if(cmd==2)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
tail++;
push(x2,y2,2,1,tail);
push(x1-1,y1-1,2,1,tail);
push(x1-1,y2,2,-1,tail);
push(x2,y1-1,2,-1,tail);
//printf("2");
}
}
solve(1,tot);
for(int i=1;i<=tail;i++) printf("%d
",ans[i]);
return 0;
} それからまだ终わっていません...私は[IOI 2001]携帯电话がこの2つの问题と同じように见えることを発见します...このTMは本当にIOIですか?こんなに水...それから私はまた新しい発见があります...この问题のデータの范囲はまるで小さいです..これは直接に2次元の木の形の配列ですることができます...その上暴力も过ごすことができるようです...私はコードを贴らないで...问题あなた达も自分で探します~
HelenKeller
2016.7.7