NOIP 2013 火柴排队
很经典的一道题了，然而以前一直懒得做Orz 离散化+树状数组求逆序对
很经典的一道题了，然而以前一直懒得做Orz 离散化+树状数组求逆序对
本来想用线段树做，但是考虑到用线段树的话pushup，pushdown函数有点复杂... 看到题目有覆盖操作立刻想到了珂朵莉树，于是现学了一波然后改了一下模板A了这道题。 (珂学是个好东西) (刷这道题全程循环夢違科(珂)学世紀2333333)
todolist清理计划--; 很久很久以前暑假留的作业= = 将年份离散化，用线段树简单的维护最值，然后依照提议判断就好。
#include <iostream>
#include <cstdio>
#define MAYBE cout << "maybe" << endl
#define TRUE cout << "true" << endl
#define FALSE cout << "false" << endl
using namespace std;
//define
const int maxn = 50000 + 5;
int year[maxn], val[maxn], tree[maxn << 2];
int n, m;
void build(int rt, int l, int r){
if(l == r){
tree[rt] = val[l];return ;
}
int mid = l + r >> 1;
build(rt << 1, l ,mid);
build(rt << 1 | 1, mid + 1, r);
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int query(int rt, int l, int r, int ll, int rr){
if(ll <= l && r <= rr){
return tree[rt];
}
int mid = l + r >> 1;
int ans = -1 * 0x7f7f7f7f;
if(ll <= mid)ans = max(ans, query(rt << 1, l, mid, ll, rr));
if(rr > mid)ans = max(ans, query(rt << 1 | 1, mid + 1, r, ll, rr));
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(register int i = 1; i <= n; ++i)cin >> year[i] >> val[i];
build(1, 1, n);
cin >> m;
while(m--){
int x,y,u,v;
cin >> y >> x;
if(y >= x) { FALSE; continue; }
u=lower_bound(year+1, year+n+1, y) - year;
v=lower_bound(year+1, year+n+1, x) - year;
if(y == year[u] && x == year[v]){
if(val[u] < val[v]) FALSE;
else if(v == u+1){
if(x == y+1)TRUE;
else MAYBE;
}
else{
int w = query(1, 1, n, u+1, v-1);
if(w >= val[v]) FALSE;
else{
if(x-y == v-u)TRUE;
else MAYBE;
}
}
}
else if(y != year[u] && x == year[v]){
if(u == v) MAYBE;
else{
int w = query(1, 1, n, u, v-1);
if(w >= val[v]) FALSE;
else MAYBE;
}
}
else if(y == year[u] && x != year[v]) {
if(v == u+1) MAYBE;
else{
int w = query(1, 1, n, u+1, v-1);
if(val[u] <= w) FALSE;
else MAYBE;
}
}
else if(y != year[u] && x != year[v]) MAYBE;
}
return 0;
}
先是写了线段树套splay,然而可耻的挂了.. 然后又写了分块,完美的tle了... 待更新
//分块tle
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
//define
const int maxn = 300 + 5;
const int maxm = 5e5 + 5;
const int inf = 0x7FFFFFFF;
int chunk_len[maxn], chunk[maxn][maxn], a[maxm], n, m, cnt, len;
void modify(int ck, int k){
a[ck] = k;
int tmp=(ck + len - 1) / len;
for(register int i = 1; i <= chunk[tmp][0]; ++i)
chunk[tmp][i] = a[(tmp - 1) * len + i];
stable_sort(chunk[tmp] + 1,chunk[tmp] + chunk_len[tmp] + 1);
}
int __lower_bound(int aa[maxn], int k){
int ll = 1, rr = aa[0];
while(ll < rr){
int mid = ll + rr >> 1;
if(aa[mid] >= k)rr = mid;
else ll = mid + 1;
}
if(aa[ll] >= k)return ll - 1;
else return ll;
}
int __sub_search(int aa[maxn], int k){
int ll = 1, rr = aa[0];
while(ll < rr){
int mid = ll + rr >> 1;
if(aa[mid + 1] <= k)ll = mid + 1;
else rr = mid;
}
if(aa[ll] <= k)return ll + 1;
else return ll;
}
int pre(int l, int r, int k){
int ll = (l + len - 1) / len;
int rr = (r + len - 1) / len;
int ans = -inf;
if(ll != rr){
for(register int i = l; i <= ll * len; ++i){
if(a[i] < k) ans = max(ans, a[i]);
}
rr++;
for(register int i = r; i >= (ll - 1) * len; --i){
if(a[i] < k) ans = max(ans, a[i]);
}
for(register int i = ll; i < rr; ++i){
if(int tmp = __lower_bound(chunk[i], k) != 0){
ans = max(chunk[i][tmp], ans);
}
}
}else{
for(register int i = l; i <= r; ++i){
if(a[i] < k){
ans = max(ans, a[i]);
}
}
}return ans;
}
int sub(int l, int r, int k){
int ll = (l + len - 1) / len;
int rr = (r + len - 1) / len;
int ans = inf;
if(ll != rr){
for(register int i = l; i <= ll * len; ++i){
if(a[i] > k) ans = min(ans, a[i]);
}
ll++;
for(register int i = r; i >= (ll - 1) * len; --i){
if(a[i] > k) ans = min(ans, a[i]);
}
for(register int i = ll; i < rr; ++i){
if(int tmp = __sub_search(chunk[i], k) != chunk_len[i] + 1){
ans = min(chunk[i][tmp], ans);
}
}
}else{
for(register int i = l; i <= r; ++i){
if(a[i] > k){
ans = min(ans, a[i]);
}
}
}return ans;
}
int rnk(int l, int r, int k){
int ll = (l + len - 1) / len;
int rr = (r + len - 1) / len;
int ans = 0;
if(ll != rr){
for(register int i = l; i <= ll * len; ++i){
if(a[i] < k) ans++;
}
ll++;
for(register int i = r; i >= (ll - 1) * len; --i){
if(a[i] < k) ans++;
}
for(register int i = ll; i < rr; ++i){
ans += __lower_bound(chunk[i], k);
}
}else{
for(register int i = l; i <= r; ++i){
if(a[i] < k){
ans++;
}
}
}return ans+1;
}
int kth(int l, int r, int k){
int ll = 0, rr = inf, ans = 0;
while(ll < rr){
int mid = ll + rr >> 1;
if(rnk(l, r, mid) > k) rr = mid;
else ll = mid+1, ans = mid;
}return ans;
}
//main
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(register int i = 1; i <=n; ++i){
cin >> a[i];
}
cnt = sqrt(n) + 2;len = cnt;
for(register int i = 1; i <= cnt; ++i){
for(register int j = 1; j <= len; ++j){
chunk[i][j] = a[(i - 1) * len + j];
}
stable_sort(chunk[i] + 1, chunk[i] + len + 1);
chunk_len[i] = len;
}
if(n % len != 0){
cnt++;chunk_len[cnt] = n % len;
for(register int i = 1; i <= chunk_len[cnt]; ++i){
chunk[cnt][i] = a[(cnt - 1) * len + i];
}
stable_sort(chunk[cnt] + 1, chunk[cnt] + chunk_len[cnt] + 1);
}
int opt, x, y, z;
while(m--){
cin >> opt;
if(opt == 1){
cin >> x >> y >> z;
cout << rnk(x, y, z) << endl;
}
else if(opt == 2){
cin >> x >> y >> z;
cout << kth(x, y, z) << endl;
}
else if(opt == 3){
cin >> x >> y;
modify(x, y);
}
else if(opt == 4){
cin >> x >> y >> z;
cout << pre(x, y, z) << endl;
}else {
cin >> x >> y >> z;
cout << sub(x, y, z) << endl;
}
}
return 0;
}
BeyondLimits: tql%%%
Polarnova: 催更
splay板子，记录一下
#include <iostream>
#include <cstdio>
using namespace std;
//define
const int maxn=1e5+5;
struct Splay{
int ch[maxn<<1][2] ,par[maxn<<1] ,cnt[maxn<<1] ,size[maxn<<1] ,val[maxn<<1] ,ntot ,trt;
int chk(int rt){return ch[par[rt]][1] == rt;}
void pushup(int rt){size[rt] = size[ch[rt][0]] + size[ch[rt][1]] + cnt[rt];}
void rotate(int rt){
int y = par[rt];
int z = par[y];
int rnk = chk(rt);
int w = ch[rt][rnk^1];
ch[y][rnk] = w; par[w] = y;
ch[z][chk(y)] = rt;par[rt] = z;
ch[rt][rnk^1] = y;par[y] = rt;
pushup(y); pushup(rt);
}
void splay(int rt,int g = 0){
while(par[rt] != g){
int y = par[rt] ,z = par[y];
if(z != g){
if(chk(rt) == chk(y))rotate(y);
else rotate(rt);
}
rotate(rt);
}
if(!g) trt = rt;
}
void find(int rt){
if(!trt) return ;
int cur = trt;
while(ch[cur][rt > val[cur]] && rt != val[cur]){
cur = ch[cur][rt > val[cur]];
}
splay(cur);
}
void insert(int rt){
int cur = trt ,p = 0;
while(cur && val[cur] != rt){
p = cur;
cur = ch[cur][rt > val[cur]];
}
if(cur){
cnt[cur]++;
}
else{
cur = ++ntot;
if(p) ch[p][rt > val[p]] = cur;
ch[cur][0] = ch[cur][1] = 0;
val[cur] = rt;
par[cur] = p;
cnt[cur] = size[cur] = 1;
}
splay(cur);
}
int kth(int k){
int cur = trt;
while(1){
if(ch[cur][0] && k <= size[ch[cur][0]]){
cur = ch[cur][0];
}
else if(k > size[ch[cur][0]] + cnt[cur]){
k -= size[ch[cur][0]] + cnt[cur];
cur = ch[cur][1];
}
else{
return cur;
}
}
}
int pre(int rt){
find(rt);
if(val[trt] < rt)return trt;
int cur = ch[trt][0];
while(ch[cur][1]) cur = ch[cur][1];
return cur;
}
int src(int rt){
find(rt);
if(val[trt] > rt)return trt;
int cur = ch[trt][1];
while(ch[cur][0]) cur = ch[cur][0];
return cur;
}
void remove(int rt){
int last = pre(rt) ,next = src(rt);
splay(last); splay(next ,last);
int del = ch[next][0];
if(cnt[del] > 1){
cnt[del]--;
splay(del);
}
else ch[next][0] = 0;
}
int get_rt(){
return size[ch[trt][0]];
}
int get_kth(int rt){
return val[kth(rt+1)];
}
int get_pre(int rt){
return val[pre(rt)];
}
int get_src(int rt){
return val[src(rt)];
}
}tree;
//main
int main(){
ios::sync_with_stdio(false);
int n,op,x;
cin>>n;
tree.insert(0x3f3f3f3f);
tree.insert(0xcfcfcfcf);
while(n--){
cin>>op>>x;
if(op == 1){
tree.insert(x);
}
if(op == 2){
tree.remove(x);
}
if(op == 3){
tree.find(x);
cout<<tree.get_rt()<<endl;
}
if(op == 4){
cout<<tree.get_kth(x)<<endl;
}
if(op == 5){
cout<<tree.get_pre(x)<<endl;
}
if(op == 6){
cout<<tree.get_src(x)<<endl;
}
}
return 0;
}