# 1 solutions

• @ 2023-8-29 23:18:14

树套bitset

``````#include<bits/stdc++.h>

#define endl '\\n'

#define pb push\_back

#define pp pop\_back

#define debug1(x) cout << #x << " = " << (x) << '\\n'

#define debug2(x) cout << #x << " = " << (x) << ' '

//#define x first

//#define y second

using namespace std;

typedef long long ll;

typedef pair<int, int> PII;

const int N = 1e4+5, M = 1e6+5;

const int MOD = 998244353, INF = 0x3f3f3f3f;

int n, m, w[N];

vector<int> v;

int get(int x) {

return lower\_bound(v.begin(), v.end(), x) - v.begin();

}

struct Node {

int l, r;

bitset<11000> t;

} tr[N << 2];

void build(int u, int l, int r) {

tr[u] = {l, r};

if(l == r) return ;

int mid = l + r >> 1;

build(u << 1, l, mid);

build(u << 1 | 1, mid + 1, r);

}

void pushup(int u, int x) {

tr[u].t[x] = tr[u << 1].t[x] | tr[u << 1 | 1].t[x];

}

void modify(int u, int p, int x, int op) {

if(tr[u].l == tr[u].r) {

if(op == 0) tr[u].t[x] = 1;

else tr[u].t[x] = 0;

return ;

}

int mid = tr[u].l + tr[u].r >> 1;

if(p <= mid) modify(u << 1, p, x, op);

else modify(u << 1 | 1, p, x, op);

pushup(u, x);

}

bitset<11000> query(int u, int l, int r) {

if(l <= tr[u].l && tr[u].r <= r) return tr[u].t;

int mid = tr[u].l + tr[u].r >> 1;

bitset<11000> ans;

if(l <= mid) ans |= query(u << 1, l, r);

if(r > mid) ans |= query(u << 1 | 1, l, r);

return ans;

}

struct Query {

char opt;

int x, y;

} Q[N];

void solve() {

cin >> n >> m;

for(int i = 1; i <= n; i ++) {

cin >> w[i];

v.push\_back(w[i]);

}

for(int i = 1; i <= m; i ++) {

cin >> Q[i].opt >> Q[i].x >> Q[i].y;

if(Q[i].opt == 'R') v.push\_back(Q[i].y);

}

sort(v.begin(), v.end());

v.erase(unique(v.begin(), v.end()), v.end());

build(1, 1, n);

for(int i = 1; i <= n; i ++) modify(1, i, get(w[i]), 0);

for(int i = 1; i <= m; i ++) {

if(Q[i].opt == 'Q') cout << query(1, Q[i].x, Q[i].y).count() << endl;

else if(Q[i].opt == 'R') {

modify(1, Q[i].x, get(w[Q[i].x]), 1);

w[Q[i].x] = Q[i].y;

modify(1, Q[i].x, get(w[Q[i].x]), 0);

}

}

}

int main() {

ios::sync\_with\_stdio(false);

cin.tie(nullptr), cout.tie(nullptr);

int t = 1;

//cin >> t;

while(t --) solve();

return 0;

}
``````
• 1

# Information

ID
2120
Time
1000ms
Memory
256MiB
Difficulty
6
Tags
(None)
# Submissions
185
Accepted
60