1
2
3
4
5
6

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

1
2

1
2

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1) 
const int N = 1e5+10;
const int M = 0; 
struct SegTree
{
private:
    struct node
    {
        int l,r;
        int lights;//亮着的灯有几盏
        bool reverse;//是否进行反转操作
        node() : l(0), r(0), lights(0), reverse(0) {};
    }tree[N<<2];
    vector<int> arr;

    void push_up(int p)
    {
        tree[p].lights = tree[ls(p)].lights + tree[rs(p)].lights;
    }
	//进行反转操作后，各值如何处理
    void apply_rev(int p)
    {
        int len = tree[p].r - tree[p].l + 1;
        tree[p].lights = len - tree[p].lights;
        //不可直接赋值false,因为并非仅当reverse = true时才进行apply操作（详见updaterev）
        tree[p].reverse = !tree[p].reverse;
    }

    void push_down(int p)
    {
        if(tree[p].reverse)
        {
            apply_rev(ls(p));
            apply_rev(rs(p));
            tree[p].reverse = false;
        }
    }
public:
    SegTree(vector<int>& _arr) : arr(_arr)
    {
        build(1,1,(int)arr.size()-1);
    }

    void build(int p,int l,int r)
    {
        tree[p].l = l;
        tree[p].r = r;
        if(r==l)
        {
            tree[p].lights = 0;
            tree[p].reverse = false;
            return;
        }
        int mid = r + l >> 1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);
    }

    void updaterev(int p,int ul,int ur)
    {
        if(tree[p].l>=ul&&tree[p].r<=ur)
        {
            apply_rev(p);
            return;
        }
        int mid = (tree[p].l + tree[p].r) >> 1;
        push_down(p);
        if(mid>=ul) updaterev(ls(p),ul,ur);
        if(mid<ur) updaterev(rs(p),ul,ur);
        push_up(p);
    }

    int querylights(int p,int ql,int qr)
    {
        if(tree[p].l >= ql && tree[p].r <= qr)
        {
            return tree[p].lights;
        }
        int mid = tree[p].l + tree[p].r >> 1;
        int res = 0;
        push_down(p);
        if(mid>=ql) res += querylights(ls(p),ql,qr);
        if(mid<qr) res += querylights(rs(p),ql,qr);
        return res;
    }
};
void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> arr(n+1,0);
    SegTree st(arr);
    while(m--)
    {
        int op;
        cin >> op;
        if(op==0)
        {
            int l,r;
            cin >> l >> r;
            st.updaterev(1,l,r);
        }
        else
        {
            int l,r;
            cin >> l >> r;
            cout << st.querylights(1,l,r) << endl;
        }
    }
}

 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
96
97
98

void solve()
{   
    int n, m;
    cin >> n >> m;
    vector<int> arr(n+1,0);
    vector<int> cl(n+1);
    vector<int> cr(n+1);
    vector<int> belong(n+1);
    vector<int> light(n+1); // 第 i 个块内亮着灯的数量
    vector<int> pre(n+1); // 前 i 个块内亮着灯的数量
    vector<int> tag(n+1,0); // 懒操作，表示这个块被重置与否
    int len, bcnt;
    auto init = [&]() -> void
    {
        len = sqrt(n);
        bcnt = (n - 1) / len + 1;
        for(int i=1;i<=bcnt;i++)
        {
            cl[i] = cr[i-1] + 1;
            cr[i] = i * len;
        }
        cr[bcnt] = n;
        for(int i=1;i<=bcnt;i++)
        {
            for(int j=cl[i];j<=cr[i];j++)
            {
                belong[j] = i;
            }
        }
    };
    init();
    // 0 灭 1 开
    auto update = [&](int ul,int ur) ->void
    {
        int bl = belong[ul],br = belong[ur];
        if(bl == br)
        {   
            for(int i=ul;i<=ur;i++)
            {   
                light[bl] -= (arr[i] ^ tag[bl]);
                arr[i] ^= 1;
                light[bl] += (arr[i] ^ tag[bl]);
            }
            for(int i=1;i<=bcnt;i++) pre[i] = pre[i-1] + light[i];
            return;
        }
        for(int i=bl+1;i<=br-1;i++)
        {
            light[i] = len - light[i];
            tag[i] ^= 1;
        }
        for(int i=ul;i<=cr[bl];i++)
        {
            light[bl] -= (arr[i] ^ tag[bl]);
            arr[i] ^= 1;
            light[bl] += (arr[i] ^ tag[bl]);
        }
        for(int i=ur;i>=cl[br];i--) 
        {
            light[br] -= (arr[i] ^ tag[br]);
            arr[i] ^= 1;
            light[br] += (arr[i] ^ tag[br]);
        }
        for(int i=1;i<=bcnt;i++) pre[i] = pre[i-1] + light[i];
    };

    auto query = [&](int ql,int qr) -> int
    {
        int bl = belong[ql],br = belong[qr];
        if(bl == br)
        {
            int ans = 0;
            for(int i=ql;i<=qr;i++) ans += (arr[i] ^ tag[bl]);
            return ans;
        }
        int ans = pre[br - 1] - pre[bl];
        for(int i=ql;i<=cr[bl];i++) ans += (arr[i] ^ tag[bl]);
        for(int i=qr;i>=cl[br];i--) ans += (arr[i] ^ tag[br]);
        return ans;
    };
    for(int i=1;i<=m;i++)
    {
        int op;
        cin >> op;
        if(op==0)
        {
            int l,r;
            cin >> l >> r;
            update(l,r);
        }
        if(op==1)
        {
            int l,r;
            cin >> l >> r;
            cout << query(l,r) << endl;
        }
    }
}