xindoo is
always here

Light oj 1080 – Binary Simulation(树状数组区间更新点查询)


题目链接

题意:

    有一字符串只包含0和1,然后又m组操作,I L R是将从L到R的字符进行翻转操作0变为1、1变为0,Q x表示询问第x的字符。

思路:

    我们只需要计算对询问的字符进行了多少次翻转,如果是偶数次,该字符变,否则翻转。对于区间的更新,我们可以使用线段树,不过对于这个题,因为只是对点的查询,而且每个节点的初始值都相同,为0,因此我们可以直接使用树状数组。下面是一个很巧妙的做法,而且很容易理解。

用了树状数组的区间更新 单点查找(一般为单点更新 区间查找)

例如 区间(2,4)加1

则Updata(2,1)   Updata(4+1,-1)

实现了更新(2,4)的值而不改变其他值

求Sum时即可得到某一点的值

//LA 1080 - Binary Simulation
//2013-04-12-18.52
#include <stdio.h>
#include <string.h>

const int maxn = 100010;
char str[maxn];
int n;
int sum[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void change(int x, int v)
{
    while (x <= n)
    {
        sum[x] += v;
        x += lowbit(x);
    }
}

int get(int x)
{
    int s = 0;
    while (x)
    {
        s += sum[x];
        x -= lowbit(x);
    }
    return s;
}

void update(int l, int r)
{
    change(l, 1);
    change(r+1, -1);
}

int main()
{
    int t, m;
    scanf("%d",&t);
    for(int i = 1; i <= t; i++)
    {
        memset(sum, 0, sizeof(sum));
        scanf("%s",&str[1]);
        scanf("%d",&m);
        n =strlen(&str[1]);
        char op;
        int l, r;
        printf("Case %d:\n",i);
        while (m--)
        {
            getchar();
            scanf("%c",&op);
            if (op == 'I')
            {
                scanf("%d %d",&l, &r);
                update(l, r);
            }
            else
            {
                scanf("%d",&l);
                if (get(l)%2 == 1)
                {
                    if (str[l] == '1')
                        puts("0");
                    else
                        puts("1");
                }
                else
                    printf("%c\n",str[l]);
            }

        }
    }
    return 0;
}


这题也可以用线段树来做,个人感觉没有必要,有兴趣的读者可以试试。


打赏
未经允许不得转载:XINDOO » Light oj 1080 – Binary Simulation(树状数组区间更新点查询)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏