比赛 树状数组练习 评测结果 AAAAAAAAAA
题目名称 人工湖 最终得分 100
用户昵称 XZDZD 运行时间 0.230 s
代码语言 C++ 内存使用 3.85 MiB
提交时间 2025-06-12 14:34:30
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5 + 10;
using namespace std;
int n, m;
vector <int> tree (N, 1);
vector <int> Tree (N);
void add (int x, int v) {
    for (; x <= n; x += x & -x) {
        Tree[x] += v;
    }
}
int query (int x) {
    int res = 0;
    for (;x > 0; x -= x & -x) {
        res += Tree[x];
    }
    return res;
}
int qlink (int a, int b) {
    if (a > b) return 0;
    else return query(b) - query(a - 1);
}
int main() {
    freopen("lakee.in","r",stdin);
    freopen("lakee.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) add(i, 1);
    
    for (int i = 1; i <= m; ++i) {
        int f, a, b; cin >> f >> a >> b;
        if (f == 0) {
            int temp = 0;
            if (a > b) swap (a, b);
            if (b == a + 1) {
                temp = a;
            }else if (a == 1 && b == n) {
                temp = n;
            }else continue;
            int v = tree[temp] ? -1 : 1;
            add(temp, v);
            tree[temp] = 1 - tree[temp];
        }
        if (f == 1) {
            if (a == b) {
                cout << "YES" << '\n';
                continue;
            }
            if (a > b) swap(a, b);
            int sum1 = 0, sum2 = 0;

            sum1 += qlink(a, b - 1);
            sum2 += qlink(1, a - 1) + qlink(b, n);

            if (sum1 == (b - a) || sum2 == n - (b - a)) {
                cout << "YES" << '\n';
            }else cout << "NO" << '\n';
        }
    }
    return 0;
}