• 13967708449
  • 1322284500@qq.com

Category Archive未分类

[HEOI2012]采花

题意:

给出n个数字,和m组询问,每次询问区间有多少种数字个数大于1….
n,m\leq 1000000

分析:

刚刚看到题目,直接想到分块,然后看数据范围GG….然后我们考虑树状数组的写法,我们先给询问按照左端点排一个序.然后我们右移左端点,然后维护树状数字…我们找到一个位置i,那么我们将其next[i]-1,next[next[i]]+1,然后区间询问就好了….
为什么是这样子呢,我们发现现在枚举了左端点,表示我们要询问的是到有段点之间的值,那么我们发现当你枚举一种颜色的位置时,没有产生贡献的区间就是这个位置和下一个位置之间的点……然后BIT维护前缀和就好了….

代码:

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define LL long long
const LL N=1e6+10;
const LL inf=0x3f3f3f3f;
const LL mod=1e9+7;
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,c,l=1;
int x[N],p[N],nxt[N],ans[N];
namespace BIT
{
    int tree[N];
    int lowbit(int now){return now&-now;}
    void change(int now,int v){for(;now<=n;now+=lowbit(now)) tree[now]+=v;}
    int sum(int now,int ret=0){for(;now;now-=lowbit(now)) ret+=tree[now];return ret;}
}
using namespace BIT;
struct Ask{int l,r,id;}ask[N];
bool cmp(Ask a,Ask b){return a.l<b.l;}
int main()
{
    read(n),read(c),read(m);
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=n;i>=1;i--) nxt[i]=p[x[i]],p[x[i]]=i;
    for(int i=1;i<=c;i++) if(nxt[p[i]]) change(nxt[p[i]],1);
    for(int i=1;i<=m;i++) read(ask[i].l),read(ask[i].r),ask[i].id=i;
    sort(ask+1,ask+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(l<ask[i].l)
        {
            if(nxt[l]) change(nxt[l],-1);
            if(nxt[nxt[l]]) change(nxt[nxt[l]],1);
            l++;
        }
        ans[ask[i].id]=sum(ask[i].r)-sum(ask[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

[JSOI2009]Count—-二维树状数组入门

题意:传送门

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

分析:

这道题,作为二维树状数字入门题还不错….二维树状数组就是对两维同时进行操作的树状数组,每一维的操作方法和一维时的一样…..不过我在写题的时候出了点小意外,先是我每次对于询问,都暴枚一维(明明题目上面写着询问少于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;
}

密码保护:2018提高组模拟赛24 Day2

这是一篇受密码保护的文章,您需要提供访问密码: