HDU 6186 CS Course（线段树区间操作）

小鱼儿 2022-06-09 11:55 144阅读 0赞

Little A has come to college and majored in Computer and Science.  
  
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.  
  
Here is the problem:  
  
You are giving n non-negative integers a1,a2,⋯,an a1,a2,⋯,an, and some queries.  
  
A query only contains a positive integer p, which means you  
are asked to answer the result of bit-operations (and, or, xor) of all the integers except ap ap.

Input

There are no more than 15 test cases.  
  
Each test case begins with two positive integers n and p  
in a line, indicate the number of positive integers and the number of queries.  
  
2≤n,q≤105 2≤n,q≤105  
  
Then n non-negative integers a1,a2,⋯,an a1,a2,⋯,an follows in a line, 0≤ai≤109 0≤ai≤109 for each i in range\[1,n\].  
  
After that there are q positive integers p1,p2,⋯,pq p1,p2,⋯,pqin q lines, 1≤pi≤n 1≤pi≤n for each i in range\[1,q\].

Output

For each query p, output three non-negative integers indicates the result of bit-operations(and, or, xor) of all non-negative integers except ap ap in a line.

Sample Input

3 3
    1 1 1
    1
    2
    3

Sample Output

1 1 0
    1 1 0
    1 1 0

题解：

题意：

给一堆数字，每次询问一个x，让你分别求除了下标为x的数字其他数字的与，或，异或运算的结果

思路：

如果x为1或者n，直接用线段树求\[2，n\]的结果或者\[1,n-1\]的结果

否则将区间分成两段，\[1,x-1\]和\[x+1,n\]然后这两段的结果进行要求的运算就好了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-7
    #define maxn 1e5+5
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    struct node
    {
        int l,r;
        int v1,v2,v3;
    }t[100005*4];
    int d1,d2,d3;//这三个为询问的结果，因为函数返回值只能有一个，所以直接定义成全局就好了
    void pushup(int k)
    {
        t[k].v1=t[lson].v1&t[rson].v1;
        t[k].v2=t[lson].v2|t[rson].v2;
        t[k].v3=t[lson].v3^t[rson].v3;
    }
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        if(l==r)
        {
            scanf("%d",&t[k].v1);
            t[k].v2=t[k].v3=t[k].v1;
            return;
        }
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
        pushup(k);
    }
    void query(int l,int r,int k)
    {
        if(t[k].l==l&&t[k].r==r)
        {
            d1=t[k].v1;
            d2=t[k].v2;
            d3=t[k].v3;
            return;
        }
        int mid=M;
        if(r<=mid)
            query(l,r,lson);
        else if(l>mid)
            query(l,r,rson);
        else
        {
            int t1,t2,t3;
            query(l,mid,lson);
            t1=d1,t2=d2,t3=d3;//暂存一下
            query(mid+1,r,rson);
            d1&=t1;
            d2|=t2;
            d3^=t3;
        }
    }
    int main()
    {
        int i,j,x,n,m,t1,t2,t3;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            Build(1,n,1);
            for(i=0;i<m;i++)
            {
                scanf("%d",&x);
                if(x==1||x==n)//假如x是端点的情况
                {
                    if(x==1)
                        query(2,n,1);
                    else
                        query(1,n-1,1);
                    printf("%d %d %d\n",d1,d2,d3);
                    continue;
                }
                query(1,x-1,1);//询问两边
                t1=d1;
                t2=d2;
                t3=d3;
                query(x+1,n,1);
                printf("%d %d %d\n",d1&t1,d2|t2,d3^t3);
            }
        }
        return 0;
    }