提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

区间更新+单点查询

查询 更新 区间 单点
2023-09-14 08:56:53 时间

F: 操作数

 

 

 

 

 

 

题解：和刷气球那题一样，判断每个位置被更新的次数，如果是奇数输出1，偶数输出0

注意：用cin会超时

 

一、线段树

//注意laz[]要和线段树数组开一样大小
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int  N = 100050;
using namespace std;
int tre[N * 4];
void pushdown(int num);
// void pushdown(int num)
// {
//     if (laz[num] != 0)
//     {
//         tre[num * 2] += laz[num];
//         tre[num * 2 + 1] += laz[num];
//         laz[num * 2] += laz[num];
//         laz[num * 2 + 1] += laz[num];
//         laz[num] = 0;
//     }
// }
void update(int num, int le, int ri, int x, int y)
{
    if (le >= x && ri <= y)
    {
        tre[num]++;
        return;
    }
    int mid = (le + ri) >> 1;
    if (tre[num])
        pushdown(num);
    if (x <= mid)
        update(num << 1, le, mid, x, y);
    if (y > mid)
        update(num << 1 | 1, mid + 1, ri, x, y);
}
void pushdown(int num)
{
    tre[num << 1] += tre[num];
    tre[num << 1 | 1] += tre[num];
    tre[num] = 0;
}
int query(int num, int le, int ri, int x)
{
    if (le == ri)
        return tre[num];
    int ans, mid = (le + ri) >> 1;
    if (tre[num])
        pushdown(num);
    if (x <= mid)
        ans = query(num << 1, le, mid, x);
    else
        ans = query(num << 1 | 1, mid + 1, ri, x);
    return ans;
}
int main()
{
    int t, n, m;
    scanf("%d%d",&n,&m);
    memset(tre, 0, sizeof(tre));
    //memset(laz, 0, sizeof(laz));//初始化延迟标记
    while (m--)
    {
        scanf("%d",&t);
        if (t == 1)
        {
            int x, y;
            scanf("%d%d",&x,&y);
            update(1, 1, n, x, y);
        }
        else
        {
            int x;
            scanf("%d",&x);
            int cnt = query(1, 1, n, x);
            if (cnt % 2 == 0)
                cout << 0 << endl;
            else
                cout << 1 << endl;
        }
    }
    return 0;
}

 

二、树状数组

树状数组区间更新，因为树状数组都是从起点开始一直更新到最后一个位置，所以在更新区间的时候要用到类似前缀和的思想

将区间[x，y]的值加z（z可正可负）

1、将区间[x，n]的值加上z

2、将区间[y，n]的值减上z

以上两步实现将区间[x，y]的值加上z

//注意laz[]要和线段树数组开一样大小
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int  N = 5000005;
using namespace std;
int n,m;
int c[N];
int lowbit(int x) 
{
    return x&-x;
}
void update(int x,int p) 
{
    while (x<=n) 
    {
        c[x]+=p;
        x+=lowbit(x);
    }
}
int sum(int x) 
{
    int ans=0;
    while (x) 
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() 
{
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));
    while(m--)
    {
        int t,x,y;
        scanf("%d",&t);
        if (t==1) 
        {
            scanf("%d%d",&x,&y);
            update(x,1);
            update(y+1,-1);
        } 
        else 
        {
            scanf("%d",&x);
            if (sum(x)%2==1) 
                printf("1\n");
            else 
                printf("0\n");
        }
    }
    return 0;
}

 

相关文章