[原创]SPOJ IITWPC4F - Gopu and the Grid Problem [线段树]【数据结构】

Tabris

CSDN数据结构SPOJ

发布于：2017年1月11日

次浏览

[原创]SPOJ IITWPC4F - Gopu and the Grid Problem [线段树]【数据结构】

2017-01-11 00:06:46 Tabris_ 阅读数：241

博客爬取于 2020-06-14 22:42:19
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54319679

题目链接：http://www.spoj.com/problems/IITWPC4F/
-------------------------------------------------------------------------------------.
IITWPC4F - Gopu and the Grid Problem
no tags

Gopu is interested in the integer co-ordinates of the X-Y plane (0<=x,y<=100000). Each integer coordinate contain a lamp, initially all the lamps are in off mode. Flipping a lamp means switching it on if it is in off mode and vice versa. Maggu will ask gopu 3 type of queries.

Type 1: x l r, meaning: flip all the lamps whose x-coordinate are between l and r (both inclusive) irrespective of the y coordinate.

Type 2: y l r, meaning: flip all the lamps whose y-coordinate are between l and r (both inclusive) irrespective of the x coordinate.

Type 3: q x y X Y, meaning: count the number of lamps which are in ‘on mode’(say this number be A) and ‘off mode’ (say this number be B) in the region where x-coordinate is between x and X(both inclusive) and y-coordinate is between y and Y(both inclusive).
Input

First line contains Q-number of queries that maggu will ask to gopu. (Q <= 10^5)

Then there will be Q lines each containing a query of one of the three type described above.
Output

For each query of 3rd type you need to output a line containing one integer A.

Example

Input:
3
x 0 1
y 1 2
q 0 0 2 2

Output:
4
-------------------------------------------------------------------------------------.
题目大意：
就是有一个横纵坐标范围均为[0,100000]的二位平面，每个位置的值只有 0/1，初始的时候均为 0.
定义三种操作，
x a b 将 x 轴坐标范围[a,b]的区域翻转，即 0/1 互换
y a b 将 y 轴坐标范围[a,b]的区域翻转，即 0/1 互换
q a b A B 查询(a,b)(A,B)范围内的区间中 1 的个数有多少。

解题思路：
因为题目提示的是整行的操作，所以很容易想到用两个数组分别标记对应行/列的翻转次数，奇数次为 1，偶数次为 0.

然后因为动态求区间和，想到树状数组，

然后发现一点，树状数组虽然能够很好的维护某一个值增减的变化，但是对于区间内翻转的变化既有增也有减，所以不可行，于是换成麻烦写的线段树维护就好了，

用区间更新就能很好的维护翻转标记了。

然后查询的操作与二维树状数组求和的操作一模一样，不再赘述。

附本题代码
-------------------------------------------------------------------------------.

# include <bits/stdc++.h>
using namespace std;
const int N = 100000+5;
typedef long long int LL;
/***************************************/
struct node {
    int l,r;
    LL  val;
    int lazy;
    int md(){return (l+r)>>1; }
    int ln(){return (r-l+1); }
}tree[N<<2][2];
# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt][xy].md())
void pushup(int rt,int xy){
    tree[rt][xy].val = tree[ll][xy].val+ tree[rr][xy].val;
}
void build(int rt,int l,int r,int xy){
    tree[rt][xy].l=l,tree[rt][xy].r=r;
    tree[rt][xy].val=0ll,tree[rt][xy].lazy=0;
    if(l==r) return ;
    build(ll,l,mid,xy);
    build(rr,mid+1,r,xy);
}
void pushdown(int rt,int xy){
    if(tree[rt][xy].lazy){
        tree[rr][xy].lazy = 1 - tree[rr][xy].lazy;
        tree[ll][xy].lazy = 1 - tree[ll][xy].lazy;
        tree[ll][xy].val  = tree[ll][xy].ln()-tree[ll][xy].val;
        tree[rr][xy].val  = tree[rr][xy].ln()-tree[rr][xy].val;
        tree[rt][xy].lazy = 0;
    }
}
void update(int rt,int L,int R,int xy){
    if(L<=tree[rt][xy].l&&tree[rt][xy].r<=R){
        tree[rt][xy].lazy = 1-tree[rt][xy].lazy;
        tree[rt][xy].val  = tree[rt][xy].ln()-tree[rt][xy].val;
        return ;
    }
    pushdown(rt,xy);
    if(L<=mid) update(ll,L,R,xy);
    if(R> mid) update(rr,L,R,xy);
    pushup(rt,xy);
}
LL query(int rt,int L,int R,int xy){
    if(L<=tree[rt][xy].l&&tree[rt][xy].r<=R){
        return tree[rt][xy].val ;
    }
    pushdown(rt,xy);
    LL ans = 0;
    if(L<=mid) ans+=query(ll,L,R,xy);
    if(R> mid) ans+=query(rr,L,R,xy);
    pushup(rt,xy);
    return ans;
}
LL getSum(int x,int y){
    //if(0>=x||0>=y) return 0ll;
    LL X=query(1,0,x,1),Y=query(1,0,y,0);
    return 1ll*X*(y-Y)+1ll*Y*(x-X);
}
int main(){
    int n,x,y,x1,x2,y1,y2;
    char ch ;
    build(1,0,100001,0);
    build(1,0,100001,1);
    scanf("%d",&n);getchar();
    for(int i=0;i<n;i++){
        scanf("%c ",&ch);
        if('x'==ch){
            scanf("%d %d",&x,&y);
            x++,y++;
            update(1,x,y,1);
        }
        else if('y'==ch){
            scanf("%d %d",&x,&y);
            x++,y++;
            update(1,x,y,0);
        }
        else {
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            x1++,x2++,y1++,y2++;
            printf("%lld\n",getSum(x2,y2)-getSum(x1-1,y2)-getSum(x2,y1-1)+getSum(x1-1,y1-1));
        }
        getchar();
    }
    return 0;
}

/**
树状数组维护x，y的区间
tree[rt][1] XXXXXXXX
tree[rt][0] YYYYYYYY
*/

本页文档最后更新于：2021年5月16日

CSDN

数据结构