Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- using namespace std;
- /** Segment Tree **/
- struct tree{
- int r,l,value = 1;
- }a[10000002];
- //查詢->左 右 邊界要小心
- int ask(int x,int y,int i){
- if(x==a[i].r&&y==a[i].l) return a[i].value;//如果邊界都符合則回傳
- //可以只判斷一個~~因為 y一定大於X 題目有說明
- else if(x>a[i*2].l) return ask(x,y,i*2+1);//如果可以直接分到右邊 就分右邊
- else if(y<=a[i*2].l) return ask(x,y,i*2);//如果可以直接分到左邊 就分左邊
- else return ask(x,a[i*2].l,i*2)*ask(a[i*2+1].r,y,i*2+1);//剩下的分開他們
- }
- int main(){
- int N,m,x,y,M,t;
- char ch;
- while(scanf("%d %d",&N,&M)!=EOF){//讀入測資
- m = log(N)/log(2)+1;//先計算 tree有幾層
- if(pow(2,m-1) != N) m++;//我會喜歡把葉子補到2的n次方 比較好計算
- for(int i=0;i<pow(2,m);i++) a[i].value = 1;//先僵值規0~(這行好像可以省略的樣子...
- for(int i=pow(2,m-1);i<pow(2,m-1)+N;i++) {
- scanf("%d",&t);
- //value 只需判斷+ - 即可
- if(t==0) a[i].value = 0;
- else if(t<0) a[i].value = -1;
- else a[i].value = 1;
- a[i].r = i-pow(2,m-1)+1;//紀錄右邊界
- a[i].l = i-pow(2,m-1)+1;//紀錄左邊界
- }
- for(int i=pow(2,m-1)+N;i<pow(2,m);i++) {
- a[i].r = i-pow(2,m-1)+1;//將我補上的葉子之左右邊界補一下
- a[i].l = i-pow(2,m-1)+1;
- }
- for(int i=pow(2,m-1)-1;i>=1;i--){//從後面往前建樹
- a[i].value = a[i*2].value*a[i*2+1].value;
- a[i].r = a[i*2].r;
- a[i].l = a[i*2+1].l;
- }
- while(M--){
- cin>>ch;//讀入指令
- if(ch=='P') {//查詢並印出
- scanf("%d %d",&x,&y);
- t = ask(x,y,1);
- if(t==0) printf("0");
- else if(t<0) printf("-");
- else if(t>0) printf("+");
- }
- else {//更新樹
- scanf("%d %d",&x,&y);
- if(y==0) a[(int)(pow(2,m-1)+x-1)].value = 0;
- else if(y<0) a[(int)(pow(2,m-1)+x-1)].value = -1;
- else a[(int)(pow(2,m-1)+x-1)].value = 1;
- for(int i=(pow(2,m-1)+x-1)/2;i>=1;i/=2)
- a[i].value =(a[i*2].value)*(a[i*2+1].value);
- }
- }
- printf("\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement