# 一无所|知的小|J f

### 题解 P4422 【[COCI2017-2018#1] Deda】

posted on 2018-12-07 19:27:03 | under 题解 |

#include<iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 200010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, x, y, z, k;
int sq;
int a[maxn], b[maxn], minn[2002];
char t;

inline void in(re int &x){
x=0;int bl = 1;char c=getchar();
while(c<'0'||c>'9'){
if(c == '-')
bl = -1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x *= bl;
}

void out(re int a){
if(a < 0) {
putchar('-');
a = -a;
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}

inline int query(int x, int y, int k) {
FOR(i, x, min(y, b[x]*sq)) //左散块
if(a[i] <= k)
return i;
FOR(i, b[x]+1, b[y]-1) { //整块
if(minn[i] > k) //如果不符合直接跳过
continue;
FOR(j, (i-1)*sq+1, i*sq) //暴力找
if(a[j] <= k)
return j;
}
if(b[x] != b[y]) //右散块
FOR(i, (b[y]-1)*sq+1, y)
if(a[i] <= k)
return i;
return -1;
}

int main(){
in(n), in(m);
sq = sqrt(n);
FOR(i, 1, sq+100)
minn[i] = 0x7fffffff;
FOR(i, 1, n)
a[i] = 0x7fffffff, b[i] = (i-1)/sq+1, minn[b[i]] = min(minn[b[i]], a[i]);
FOR(i, 1, m) {
cin >> t;
if(t == 'M') {
in(x), in(y); // y改成x;
a[y] = x;
minn[b[y]] = min(minn[b[y]], x); //维护最小值
}
else {
in(k), in(x);
out(query(x, n, k));
putchar(10);
}
}

}