POJ-1195 Mobile phones

题目链接：https://vjudge.net/problem/POJ-1195#author=muchen1026

思路

二维树状数组的模板题

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,S;
int tr[1111][1111];

int lowbit(int x){
    return x&-x;
}
void add(int x,int y,int v){
    for(int i = x;i<=S;i += lowbit(i)){
        for(int j = y;j<=S;j += lowbit(j)){
            tr[i][j] += v;
        }
    }
}
ll pre_sum(int x,int y){
    ll sum = 0;
    for(int i = x;i>=1;i -= lowbit(i)){
        for(int j = y;j>=1;j -= lowbit(j)){
            sum += tr[i][j];
        }
    }
    return sum;
}
ll query(int x1,int y1,int x2,int y2){
    return pre_sum(x2,y2) - pre_sum(x1-1,y2) - pre_sum(x2,y1-1) + pre_sum(x1-1,y1-1);
}
int main(){
    // debug;
    ios;
    int op,x1,y1,x2,y2,v;
    cin>>N;
    do{
        if(N == 3) break;
        if(N == 0) {
            memset(tr,0,sizeof tr);
            cin>>S;
        }else{
            if(N == 1) {
                cin>>x1>>y1>>v; x1++,y1++;
                add(x1,y1,v);
            }else{
                cin>>x1>>y1>>x2>>y2; x1++,y1++,x2++,y2++;
                cout<<query(x1,y1,x2,y2)<<'\n';
            }
        }
    }while(cin>>N);
    return 0;
}