寒假集训队训练题 线段树+树状数组

A - 敌兵布阵

题目大意：对区间中单个元素进行加减操作，并求区间和

解题思路：树状数组的标准模板

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int bit[50001];
int N;
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=bit[x];
        x-=x&-x;
    }
    return sum;
}
void add(int x,int index)
{
    while(index<=N)
    {
        bit[index]+=x;
        index+=index&-index;
    }
}
void gets_(char a[])
{
    int i=0;
    while((a[i]=getchar())!=' ' && a[i]!='\n')
        i++;
}
int main()
{
    int t,num=0,i,a,b,temp;
    char ch[10];
    scanf("%d",&t);
    while(t--)
    {
        fill(bit,bit+50001,0);
        scanf("%d",&N);
        for(i=1;i<=N;i++)
            {
                scanf("%d",&temp);
                add(temp,i);
                //printf("%d ",bit[i]);
            }
        //printf("bit[4]=%d\n",bit[4]);
        printf("Case %d:\n",++num);
        while(true)
        {
            getchar();
            gets_(ch);
            if(ch[0]=='Q')
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",sum(b)-sum(a-1));
                continue;
            }
            else if(ch[0]=='A')
            {
                scanf("%d%d",&a,&b);
                add(b,a);
                continue;
            }
            else if(ch[0]=='S')
            {
                scanf("%d%d",&a,&b);
                add(-b,a);
                continue;
            }
            else break;
        }
    }
    return 0;
}

B - Color the ball

题目大意：对区间中每一个元素进行加1操作，多组操作后输出所有元素

解题思路：树状数组对每组区间首元素进行加1，这样求sum（i）就可以得到第i个元素的值了

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int bit[100001];
int N;
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=bit[x];
        x-=x&-x;
    }
    return sum;
}
void add(int x,int index)
{
    while(index<=N)
    {
        bit[index]+=x;
        index+=index&-index;
    }
}
int main()
{
    int i,a,b;
    while(scanf("%d",&N),N)
    {
        fill(bit,bit+100001,0);
        for (i=0;i<N;i++)
            {
                scanf("%d%d",&a,&b);
                add(1,a);
                add(-1,b+1);
            }
        for (i=1;i<N;i++)
            printf("%d ",sum(i));
        printf("%d",sum(N));
        printf("\n");
    }
    return 0;
}

C - Mayor's posters

题目大意：存在先后顺序的对区间进行覆盖操作，求最后可以看见多少种不同的覆盖

解题思路：每组操作的区间很大，所以进行离散化，然后是对离散化后的操作构造线段树，进行区间的更新，对应操作区间赋值为操作次数，建立bool数组记录不同的操作

AC代码：

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstring>
#include <cmath>
#define MAXN 10005
using namespace std;
int li[MAXN],ri[MAXN],x[MAXN<<2],st[MAXN<<4];
int N,ans;
bool all[MAXN<<2];
void pushdown(int k)
{
    st[k<<1]=st[k<<1|1]=st[k];
    st[k]=-1;
}
void update(int l,int r,int L,int R,int k,int c)
{
    if (l<=L && R<=r)
    {
        st[k]=c;
        return;
    }
    int m_=(L+R)>>1;
    if (st[k]!=-1) pushdown(k);
    if (m_>=l) update(l,r,L,m_,k<<1,c);
    if (m_<r) update(l,r,m_+1,R,k<<1|1,c);
}
void query(int l,int r,int k)
{
    if (r==l)
    {
        if (st[k]!=-1 && !all[st[k]])
        {
            ans++;
            all[st[k]]=true;
        }
        return;
    }
    if (st[k]!=-1) pushdown(k);
    int m_=(l+r)>>1;
    query(l,m_,k<<1);
    query(m_+1,r,k<<1|1);
}
int main()
{
    int i,a,b,t,m,num=0;
    scanf("%d",&t);
    while(t--)
    {
        fill(all,all+(MAXN<<2),false);
        fill(st,st+(MAXN<<4),-1);
        num=0;
        scanf("%d",&N);
        for (i=0; i<N; i++)
        {
            scanf("%d%d",&li[i],&ri[i]);
            x[++num]=li[i];
            x[++num]=ri[i];
        }
        sort(x+1,x+num+1);
        //ÀëÉ¢»¯
        for (m=1,i=2; i<=num; i++)
            if (x[i]!=x[i-1]) x[++m]=x[i];
        for(i=m; i>1; i--)
            if (x[i]-x[i-1]>1) x[++m]=x[i]-1;
        sort(x+1,x+m+1);
        for (i=0; i<N; i++)
        {
            int *p=&x[0];
            int l=lower_bound(x+1,x+m+1,li[i])-p;
            int r=lower_bound(x+1,x+m+1,ri[i])-p;
            update(l,r,1,m,1,i+1);
        }
        ans=0;
        query(1,m,1);
        printf("%d\n",ans);
    }
    return 0;
}