document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. using namespace std;
  5. /**    Segment Tree    **/
  6. struct tree{
  7.     int r,l,value = 1;
  8. }a[10000002];
  9.  
  10. //查詢->左 右 邊界要小心
  11. int ask(int x,int y,int i){
  12.     if(x==a[i].r&&y==a[i].l)    return a[i].value;//如果邊界都符合則回傳
  13.  
  14.     //可以只判斷一個~~因為 y一定大於X  題目有說明
  15.     else if(x>a[i*2].l)  return ask(x,y,i*2+1);//如果可以直接分到右邊  就分右邊
  16.     else if(y<=a[i*2].l)  return ask(x,y,i*2);//如果可以直接分到左邊  就分左邊
  17.  
  18.     else return ask(x,a[i*2].l,i*2)*ask(a[i*2+1].r,y,i*2+1);//剩下的分開他們
  19. }
  20.  
  21. int  main(){
  22.     int N,m,x,y,M,t;
  23.     char ch;
  24.     while(scanf("%d %d",&N,&M)!=EOF){//讀入測資
  25.         m = log(N)/log(2)+1;//先計算 tree有幾層
  26.         if(pow(2,m-1) != N)   m++;//我會喜歡把葉子補到2的n次方  比較好計算
  27.         for(int i=0;i<pow(2,m);i++)    a[i].value = 1;//先僵值規0~(這行好像可以省略的樣子...
  28.         for(int i=pow(2,m-1);i<pow(2,m-1)+N;i++)    {
  29.             scanf("%d",&t);
  30.             //value 只需判斷+ - 即可
  31.             if(t==0)    a[i].value = 0;
  32.             else if(t<0)    a[i].value = -1;
  33.             else a[i].value = 1;
  34.             a[i].r = i-pow(2,m-1)+1;//紀錄右邊界
  35.             a[i].l = i-pow(2,m-1)+1;//紀錄左邊界
  36.         }
  37.         for(int i=pow(2,m-1)+N;i<pow(2,m);i++)    {
  38.             a[i].r = i-pow(2,m-1)+1;//將我補上的葉子之左右邊界補一下
  39.             a[i].l = i-pow(2,m-1)+1;
  40.         }
  41.  
  42.         for(int i=pow(2,m-1)-1;i>=1;i--){//從後面往前建樹
  43.             a[i].value = a[i*2].value*a[i*2+1].value;
  44.             a[i].r = a[i*2].r;
  45.             a[i].l = a[i*2+1].l;
  46.         }
  47.  
  48.  
  49.         while(M--){
  50.             cin>>ch;//讀入指令
  51.             if(ch==\'P\') {//查詢並印出
  52.                 scanf("%d %d",&x,&y);
  53.                 t = ask(x,y,1);
  54.                 if(t==0)    printf("0");
  55.                 else if(t<0)    printf("-");
  56.                 else if(t>0)    printf("+");
  57.             }
  58.             else   {//更新樹
  59.                 scanf("%d %d",&x,&y);
  60.                 if(y==0)    a[(int)(pow(2,m-1)+x-1)].value = 0;
  61.                 else if(y<0)    a[(int)(pow(2,m-1)+x-1)].value = -1;
  62.                 else a[(int)(pow(2,m-1)+x-1)].value = 1;
  63.  
  64.                 for(int i=(pow(2,m-1)+x-1)/2;i>=1;i/=2)
  65.                     a[i].value =(a[i*2].value)*(a[i*2+1].value);
  66.             }
  67.         }
  68.         printf("\\n");
  69.     }
  70. }
');