关于快读 fread 炸裂???

回复帖子

@Accoty_AM 2019-12-03 11:15 回复

rt

这个fread能过 A + B problem

粘到这题上直接挂了

求解

这是代码

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rg register
char ss[1<<17], * A = ss, * B = ss;
inline char gc(){ if(A == B){ B = (A = ss) + fread(ss, 1, 1<<17, stdin); if(A == B) return EOF; } return * A++; }
//#define gc getchar
inline int read(){
    rg char ch = gc();
    rg int x = 0, f = 0;
    while(! isdigit(ch)) f |= (ch == '-'), ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? -x : x;
}
#define al 0.7
const int N = 1e5 + 5;
int fa[N];
int find(int x){
    return x ^ fa[x] ? fa[x] = find(fa[x]) : x;
}
int n, m, q;
struct node{
    node *ls, *rs;
    int sz;
    int val, id;
    inline bool isbad(){
        return (ls ? ls -> sz : 0) > sz * al + 5 || (rs ? rs -> sz : 0) > sz * al + 5;
    }
    inline void redef(){ sz = 1; ls = rs = NULL; }
    inline void up(){
        sz = 1;
        if(ls) sz += ls -> sz;
        if(rs) sz += rs -> sz;
    }
}pool[N], *tail = pool, *rt[N], **badtag;
void insert(node * &p, node * &toadd){
    if(!p){
        p = toadd;
        return;
    }
    ++ p -> sz;
    if(toadd -> val <= p -> val) insert(p -> ls, toadd);
    else insert(p -> rs, toadd);
    if(p -> isbad()) badtag = &p;
//  else if(badtag){ //没有删除操作 
//      p -> sz -= (*badtag) -> sz - (*badtag) -> cnt;
//  }
}
void dfs(node *p, vector<node*> &v){
    if(!p) return;
    dfs(p -> ls, v);
    v.push_back(p);
    dfs(p -> rs, v);
} 
node * build(int l, int r, vector<node *> &v){
    if(l > r) return NULL;
    int mid = (l + r) >> 1;
    node *p = v[mid];
    p -> ls = build(l, mid - 1, v);
    p -> rs = build(mid + 1, r, v);
    p -> up();
    return p;
}
inline void ins(node * &p, node * &toadd){
    badtag = NULL;
    insert(p, toadd);

    if(badtag){
        vector<node*> v;
        dfs(*badtag, v);
        *badtag = build(0, v.size() - 1, v);
    }
}
void work(node * p, node * &toadd){
    if(!p) return;
    work(p -> ls, toadd);
    work(p -> rs, toadd);
    p -> redef();
    ins(toadd, p);
}
inline int kth(node * p, int k){
    while(p){
        if((p -> ls ? p -> ls -> sz : 0) >= k) p = p -> ls;
        else if((p -> ls ? p -> ls -> sz : 0) + 1 == k) return p -> id;
        else k -= (p -> ls ? p -> ls -> sz : 0) + 1, p = p -> rs;
    }
    return 0;
}
signed main(){
    n = read(); m = read();
    for(int i = 1; i <= n; ++i) fa[i] = i, rt[i] = ++tail, rt[i] -> val = read(), rt[i] -> id = i, rt[i] -> sz = 1;
    for(int x, y, i = 1; i <= m; ++i){
        x = find(read()), y = find(read());
        if(x ^ y){
            if(rt[x] -> sz < rt[y] -> sz)
                work(rt[x], rt[y]), fa[x] = y;
            else
                work(rt[y], rt[x]), fa[y] = x;
        }
    }
    q = read();
    char op;
    for(int x, y, i = 1; i <= q; ++i){
        scanf("%s", &op); x = read(), y = read();
        if(op == 'Q'){
            x = find(x);
            if(y > rt[x] -> sz){ puts("-1"); continue; }
            printf("%d\n", kth(rt[x], y));
        }else{
            x = find(x); y = find(y);
            if(x ^ y){
                if(rt[x] -> sz < rt[y] -> sz)
                    work(rt[x], rt[y]), fa[x] = y;
                else
                    work(rt[y], rt[x]), fa[y] = x;
            }
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。