【JSOI2009】计数问题

2021-02-17 16:16

阅读：647

标签：void mes ios hide lap mem closed 计数 math

题目链接

开颜色种类个二维树状数组，维护前缀和，单点修改、子矩阵查询。

注意读入的顺序，是$x_1\; x_2\; y_1\; y_2$而不是$x_1\; y_1\; x_2\; y_2$。

代码（100分）：

#include
#include
#include
#include
#include
#include
#include
#include
#includeset>
#define IL inline
#define RG register
#define _1 first
#define _2 second
using namespace std;
const int N=300;
const int M=100;

    int n,m,q,a[N+3][N+3];
    int s[M+3][N+3][N+3];
    
IL int lowbit(int x){
    return x&(-x);
}
    
IL void mdfm(int k,int p,int q,int x){
    for(;qlowbit(q))
        s[k][p][q]+=x;
}

IL void mdfn(int k,int p,int q,int x){
    for(;plowbit(p))
        mdfm(k,p,q,x);
}

IL int qrym(int k,int p,int q){
    int ret=0;
    for(;q;q-=lowbit(q))
        ret+=s[k][p][q];
    return ret;
}

IL int qryn(int k,int p,int q){
    int ret=0;
    for(;p;p-=lowbit(p))
        ret+=qrym(k,p,q);
    return ret;
}

IL int qry(int x1,int y1,int x2,int y2,int c){
    return qryn(c,x2,y2)-qryn(c,x1-1,y2)-qryn(c,x2,y1-1)+qryn(c,x1-1,y1-1);
}

IL void dat_init(){
    memset(s,0,sizeof s);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i)
        for(int j=1;j)
            scanf("%d",&a[i][j]);
            
    dat_init();
    for(int i=1;i)
        for(int j=1;j)
            mdfn(a[i][j],i,j,1);
            
    scanf("%d",&q);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            
            mdfn(a[x][y],x,y,-1);
            mdfn(c,x,y,1);
            a[x][y]=c;
            
        }
        else {
            int x1,x2,y1,y2,c;
            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
            
            printf("%d\n",qry(x1,y1,x2,y2,c));
            
        }
        
    }

    return 0;

}

View Code

【JSOI2009】计数问题

标签：void mes ios hide lap mem closed 计数 math

原文地址：https://www.cnblogs.com/Hansue/p/12954871.html

上一篇：linux安装python3.6.5

下一篇：Net HttpClient 扩展方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【JSOI2009】计数问题
文章链接：http://soscw.com/index.php/essay/56636.html

亲，登录后才可以留言！

【JSOI2009】计数问题

题目链接

评论

热门文章

推荐文章

最新文章

置顶文章