#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 300001;
const ll VMAX = 26;
const ll INF = (1LL << 55);
const ll MOD = 90000000000000001;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;
vector <int> aib[NMAX * 4 + 4];
vector <int> nrm[NMAX * 4 + 4];
void baga(int node, int val, int x) {
int poz = lower_bound(nrm[node].begin(), nrm[node].end(), val) - nrm[node].begin();
poz++;
for(; poz < aib[node].size(); poz += poz&(-poz)) {
aib[node][poz] += x;
}
}
int query(int node, int x) {
int val = 0;
int poz = upper_bound(nrm[node].begin(), nrm[node].end(), x) - nrm[node].begin();
poz++;
poz--;
if(poz == 0)
return 0;
for(; poz > 0; poz -= poz&(-poz)) {
val += aib[node][poz];
if(poz == 0)
break;
}
return val;
}
void update(int node, int st, int dr, int a, int b, int val) {
baga(node, b, val);
if(st == dr) {
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
update(node * 2, st, mid, a, b, val);
else
update(node * 2 + 1, mid + 1, dr, a, b, val);
}
int bigger(int node, int st, int dr, int x1, int x2, int y) {
if(x1 <= st && dr <= x2 && nrm[node].size()) {
return query(node, nrm[node].back()) - query(node, y);
}
int mid = (st + dr) / 2;
int sol = 0;
if(x1 <= mid)
sol += bigger(node * 2, st, mid, x1, x2, y);
if(x2 > mid)
sol += bigger(node * 2 + 1, mid + 1, dr, x1, x2, y);
return sol;
}
int smaller(int node, int st, int dr, int x1, int x2, int y) {
if(x1 <= st && dr <= x2) {
return query(node, y);
}
int mid = (st + dr) / 2;
int sol = 0;
if(x1 <= mid)
sol += smaller(node * 2, st, mid, x1, x2, y);
if(x2 > mid)
sol += smaller(node * 2 + 1, mid + 1, dr, x1, x2, y);
return sol;
}
void build(int node, int st, int dr, int a, int b) {
nrm[node].push_back(b);
if(st == dr) {
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
build(node * 2, st, mid, a, b);
else
build(node * 2 + 1, mid + 1, dr, a, b);
}
int v[NMAX];
struct ura{
int t, a, b;
};
ura queries[NMAX];
int cv[NMAX];
vector <int> ff;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, i;
cin >> n >> m;
for(i = 1; i <= n; i++){
cin >> v[i];
ff.push_back(v[i]);
cv[i] = v[i];
}
for(i = 1; i <= m; i++){
ura x;
cin >> x.t;
cin >> x.a;
if(x.t == 1){
cin >> x.b;
ff.push_back(x.b);
}else{
ff.push_back(x.a);
}
queries[i] = x;
}
sort(ff.begin(), ff.end());
map <int, int> nn;
int cnt = 0;
for(int i = 0; i < ff.size(); i++){
if(i == 0 || ff[i] != ff[i - 1])
cnt++;
nn[ff[i]] = cnt;
}
for(i = 1; i <= n; i++){
v[i] = cv[i] = nn[v[i]];
}
for(i = 1; i <= m; i++){
if(queries[i].t == 1){
queries[i].b = nn[queries[i].b];
}else{
queries[i].a = nn[queries[i].a];
}
}
for(i = 1; i < n; i++){
build(1, 1, NMAX, v[i], v[i + 1]);
}
for(i = 1; i <= m; i++){
ura x = queries[i];
if(x.t == 1){
cv[x.a] = x.b;
if(x.a > 1)
build(1, 1, NMAX, cv[x.a - 1], cv[x.a]);
if(x.a < n)
build(1, 1, NMAX, cv[x.a], cv[x.a + 1]);
}
}
for(i = 1; i <= NMAX * 4; i++){
aib[i].resize(nrm[i].size() + 1, 0);
}
for(i = 1; i < n; i++){
update(1, 1, NMAX, v[i], v[i + 1], 1);
}
for(i = 1; i <= m; i++){
ura x = queries[i];
if(x.t == 1){
int prv = v[x.a];
v[x.a] = x.b;
if(x.a > 1){
update(1, 1, NMAX, v[x.a - 1], prv, -1);
update(1, 1, NMAX, v[x.a - 1], v[x.a], 1);
}
if(x.a < n){
update(1, 1, NMAX, prv, v[x.a + 1], -1);
update(1, 1, NMAX, v[x.a], v[x.a + 1], 1);
}
}else{
int t = x.a;
int aa = 0;
if(t > 1){
aa = bigger(1, 1, NMAX, 1, t - 1, t);
}
cout << aa + smaller(1, 1, NMAX, t + 1, NMAX, t) << "\n";
}
}
return 0;
}
Compilation message
game.cpp: In function 'void baga(int, int, int)':
game.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(; poz < aib[node].size(); poz += poz&(-poz)) {
| ~~~~^~~~~~~~~~~~~~~~~~
game.cpp: In function 'int main()':
game.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i < ff.size(); i++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
94160 KB |
Output is correct |
| 2 |
Runtime error |
150 ms |
191856 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
94160 KB |
Output is correct |
| 2 |
Runtime error |
150 ms |
191856 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
94160 KB |
Output is correct |
| 2 |
Runtime error |
150 ms |
191856 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
