[TIOJ] 1869. 堆石子遊戲
題目連結:http://tioj.infor.org/problems/1869
本題我一開始以為可以開個N棵線段樹之類的,結果我就TLE了QAQ,後來想想才發現N棵線段樹的話,複雜度是$O(Q N \log N)$難怪會TLE,想了想發現似乎可以樹套樹(二維BIT),畢竟他只有區間和跟單點修改,那就直接做吧XD,複雜度$O(Q \log ^2 N)$
本題我一開始以為可以開個N棵線段樹之類的,結果我就TLE了QAQ,後來想想才發現N棵線段樹的話,複雜度是$O(Q N \log N)$難怪會TLE,想了想發現似乎可以樹套樹(二維BIT),畢竟他只有區間和跟單點修改,那就直接做吧XD,複雜度$O(Q \log ^2 N)$
#include <bits/stdc++.h>
using namespace std;
#define N 1024
#define lowbit(x) (x)&(-x)
int BIT[N+10][N+10]={0};
int n;
void edit(int,int,int);
int query(int,int);
int main(){
scanf("%d",&n);
int type;
while(scanf("%d",&type)!=EOF){
if(type==1){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++,y++;
edit(x,y,z);
}else{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1++,y1++,x2++,y2++;
int s = query(x2,y2) + query(x1-1,y1-1) - query(x1-1,y2) - query(x2,y1-1);
printf("%d\n",s);
}
}
return 0;
}
void edit(int x,int y,int v){
while(x<=n){
int yy=y;
while(yy<=n){
BIT[x][yy]+=v;
yy+=lowbit(yy);
}
x+=lowbit(x);
}
}
int query(int x,int y){
int sum=0;
while(x>0){
int yy=y;
while(yy>0){
sum+=BIT[x][yy];
yy-=lowbit(yy);
}
x-=lowbit(x);
}
return sum;
}
留言
張貼留言