题意:传送门

给出一个矩阵,每个点上有颜色,支持单点修改颜色,区间询问颜色个数….

分析:

这道题,作为二维树状数字入门题还不错….二维树状数组就是对两维同时进行操作的树状数组,每一维的操作方法和一维时的一样…..不过我在写题的时候出了点小意外,先是我每次对于询问,都暴枚一维(明明题目上面写着询问少于5000,然后数据里面200000,哼╭(╯^╰)╮),然后妥妥的TLE,接着就是lowbit,部分写错…..
原先的修改询问

for(;x<=n;x+=lowbit(x)) 
        for(;y<=m;y+=lowbit(y)) 
                xx[col][x][y]+=k;

后来发现我直接修改了y,导致后面枚举的x都没有用了,然后就改成了这样

for(;x<=n;x+=lowbit(x))
        for(int i=y;i<=m;i+=lowbit(i)) 
                xx[col][x][i]+=k;

然后妥妥的AC了…..(mdzz,艹)

代码:

#pragma GCC optimise(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e6+10;
const LL mod=998244353;
const double eps=1e-12;
#define y1 zdwshdgh
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,q;
namespace BIT
{
    int xx[110][310][310];
    int lowbit(int now){return now&-now;}
    void change(int col,int x,int y,int k) {for(;x<=n;x+=lowbit(x)) for(int i=y;i<=m;i+=lowbit(i)) xx[col][x][i]+=k;}
    int query(int col,int x,int y,int ret=0)
    {
        if(!y||!x) return 0;
        for(;x;x-=lowbit(x))
            for(int i=y;i;i-=lowbit(i)) 
                ret+=xx[col][x][i];
        return ret;
    }
}
using namespace BIT;
int coll[310][310];
signed main() 
{
    read(n),read(m);
    for(int i=1,x;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(coll[i][j]),change(coll[i][j],i,j,1);
    read(q);
    for(int cas=1;cas<=q;cas++)
    {
        int opt,x1,y1,x2,y2,k;
        read(opt);
        if(opt==1)
        {
            read(x1),read(y1),read(k);
            change(coll[x1][y1],x1,y1,-1);
            coll[x1][y1]=k;
            change(coll[x1][y1],x1,y1,1);
        }
        else 
        {
            read(x1),read(x2),read(y1),read(y2),read(k);
            printf("%d\n",query(k,x2,y2)-query(k,x2,y1-1)-query(k,x1-1,y2)+query(k,x1-1,y1-1));
        }
    }
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注