lightoj1080

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

27 8月 2015

1080 - Binary Simulation

'I i j' which means invert the bit from i to j (inclusive)Given a binary number, we are about to do some operations on the number. Two types of operations can be here.

'Q i' answer whether the i^th bit is 0 or 1

The MSB (most significant bit) is the first bit (i.e. i=1). The binary number can contain leading zeroes.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a binary integer having length n (1 ≤ n ≤ 10⁵). The next line will contain an integer q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form 'I i j' where i, j are integers and 1 ≤ i ≤ j ≤ n. Or the query will be in the form 'Q i' where i is an integer and 1 ≤ i ≤ n.

Output

For each case, print the case number in a single line. Then for each query 'Q i' you have to print 1 or 0 depending on the i^th bit.

Sample Input

Output for Sample Input

200110011006I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

1011110111

I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

Case 1:011

Case 2:

Note

Dataset is huge, use faster i/o methods.

题目类型：线段树

算法分析：需要使用lazy标记来进行区间修改，lazy布尔数组当为false时表示当前区间没有翻转，而true表示当前区间元素需要翻转。由于本题要进行单点查询，所以可以在查询到叶子节点后再判断lazy，且不需要PushUp

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100000 + 66;

bool lazy[maxn<<2];
char sum[maxn];

void PushDown (int rt)
{
    if (lazy[rt])
    {
        lazy[rt<<1] = !lazy[rt<<1];
        lazy[rt<<1|1] = !lazy[rt<<1|1];
        lazy[rt] = !lazy[rt];
    }
}


void UpDate (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        lazy[rt] = !lazy[rt];
        return ;
    }

    int m = (l + r) >> 1;
    PushDown (rt);

    if (L <= m)
        UpDate (lson, L, R);

    if (R > m)
        UpDate (rson, L, R);

}

int Query (int rt, int l, int r, int val)
{
   if (l == r)
   {
       if (lazy[rt])
       {
           sum[val] = !(sum[val] - '0') + '0';
           lazy[rt] = !lazy[rt];
       }

       return sum[val] - '0';
   }

    int m = (l + r) >> 1;
    PushDown (rt);

   if (val <= m)
        return Query (lson, val);

   else
        return Query (rson, val);
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);

        memset (lazy, false, sizeof (lazy));
        scanf ("%s", sum + 1);

        int q, len = strlen (sum + 1);

        scanf ("%d", &q);

        int i;
        char cmd[6];
        for (i = 0; i < q; i++)
        {
            scanf ("%s", cmd);
            if (cmd[0] == 'I')
            {
                int val_a, val_b;
                scanf ("%d%d", &val_a, &val_b);
                UpDate (1, 1, len, val_a, val_b);
            }

            else
            {
                int val;
                scanf ("%d", &val);
                printf ("%d\n", Query (1, 1, len, val));
            }
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100000 + 66;

bool lazy[maxn<<2];

char sum[maxn];

void PushDown (int rt)

{

if (lazy[rt])

{

lazy[rt<<1] = !lazy[rt<<1];

lazy[rt<<1|1] = !lazy[rt<<1|1];

lazy[rt] = !lazy[rt];

}

void UpDate (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

{

lazy[rt] = !lazy[rt];

return ;

}

int m = (l + r) >> 1;

PushDown (rt);

if (L <= m)

UpDate (lson, L, R);

if (R > m)

UpDate (rson, L, R);

}

int Query (int rt, int l, int r, int val)

{

if (l == r)

{

if (lazy[rt])

{

sum[val] = !(sum[val] - '0') + '0';

lazy[rt] = !lazy[rt];

}

return sum[val] - '0';

}

int m = (l + r) >> 1;

PushDown (rt);

if (val <= m)

return Query (lson, val);

else

return Query (rson, val);

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

memset (lazy, false, sizeof (lazy));

scanf ("%s", sum + 1);

int q, len = strlen (sum + 1);

scanf ("%d", &q);

int i;

char cmd[6];

for (i = 0; i < q; i++)

{

scanf ("%s", cmd);

if (cmd[0] == 'I')

{

int val_a, val_b;

scanf ("%d%d", &val_a, &val_b);

UpDate (1, 1, len, val_a, val_b);

}

else

{

int val;

scanf ("%d", &val);

printf ("%d\n", Query (1, 1, len, val));

}

return 0;

}

lightoj1078

lightoj1083

超客的水墨烟雨

lightoj1080

Input

Output

Sample Input

Output for Sample Input

Note

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
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