C++P-PJ 2155-Mタリックス[データ構造][ツリー配列]

4515 ワード

二次元ツリー配列+フォーク
区間修正は単点修正になります.
単点検索はもともと区間検索と見なされます.
そこで本題は解ける
PS:どうして関数がパラメータを伝えるのか分かりませんが、変数を伝えると奇異な問題が発生します.
読み込んで単独で書きました.また循環の初期化は、あえて変数のセットを多く定義しました.頭が大きいです.
とりあえずこの書き方を標準的な書き方としてみましょう.
 
#include <set>
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN=1001;
int t[MAXN][MAXN],n;
int lb(int i){return i&-i;}
void init(){memset(t,0,sizeof(t));}
void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lb(i))for(int j=y;j<=n;j+=lb(j))t[i][j]+=v;
}
int sum(int x,int y){
    int ans=0;for(int i=x;i;i-=lb(i))for(int j=y;j;j-=lb(j))ans+=t[i][j];return ans;
}
int a,b,c,d,x,T;char s[5];
void C(){cin>>a>>b>>c>>d;add(a,b,1),add(c+1,b,1),add(a,d+1,1),add(c+1,d+1,1);}
void Q(){cin>>a>>b;cout<2<<endl;}

int main(){
    for(scanf("%d",&x);x--;x?puts(""):0){
        scanf("%d%d",&n,&T),init();
        while(T--)scanf("%s",s),s[0]=='C'?C():Q();
    }
   return 0; }