[原创]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,100000]的二位平面 ,每个位置的值只有0/1,初始的时候均为0.
定义三种操作,
x a b 将x轴坐标范围[a,b][a,b]的区域翻转,即0/1互换
y a b 将y轴坐标范围[a,b][a,b]的区域翻转,即0/1互换
q a b A B 查询(a,b)(A,B)(a,b)(A,B)范围内的区间中1的个数有多少.

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# 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
*/