字符读入为什么用getchar会TLE啊。。。。

回复帖子

@Akrain 2019-09-06 20:05 回复

用了getchar()就TLE

换成了字符串读入就过了,咕咕咕.....

@Akrain 2019-09-06 20:18 回复 举报
#include<algorithm>
#include<iostream>
#include<cstdio>
#define MAX 100005
using namespace std;
int bel[MAX];
struct BST{
    int root[MAX],tot;
    struct Tree{
        int ch[2];
        int val,size,fa,pos;
    }tree[MAX];
    void pushup(int x){
        tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;
        return;
    }
    void rotate(int x){
        int fa=tree[x].fa;int fra=tree[fa].fa;
        bool son=(tree[fa].ch[1]==x);
        tree[x].fa=fra;tree[fa].fa=x;
        tree[fra].ch[tree[fra].ch[1]==fa]=x;
        tree[fa].ch[son]=tree[x].ch[son^1];
        tree[tree[x].ch[son^1]].fa=fa;
        tree[x].ch[son^1]=fa;
        pushup(fa);pushup(x);
        return;
    }
    void splay(int x,int tar,int to){
        int u=root[to];
        while(u&&tar!=tree[x].fa){
            int fa=tree[x].fa;int fra=tree[fa].fa;
            if(tar!=fra)
                (tree[fra].ch[1]==fa)^(tree[fa].ch[1]==x)?rotate(x):rotate(fa);
            rotate(x);
        }
        if(!tar)
            root[to]=x;
        return;
    }
    void insert(int x,int to,int pos,int use,bool opt){
        int u=root[to],fa=0;
        while(u&&tree[u].val!=x){
            fa=u;
            u=tree[u].ch[tree[u].val<x];
        }
        if(!opt)
            u=++tot;
        else
            u=use;
        tree[u].val=x;
        tree[u].fa=fa;
        tree[u].size=1;
        tree[u].pos=pos;
        tree[fa].ch[x>tree[fa].val]=u;
        splay(u,0,to);
        return;
    }
    int kth(int x,int to){
        int u=root[to];
        if(tree[u].size<x)
            return -1;
        while(19260817){
            int l=tree[u].ch[0];
            if(tree[l].size+1==x)
                return tree[u].pos;
            else if(tree[l].size<x){
                x-=tree[l].size+1;
                u=tree[u].ch[1];
            }
            else
                u=l;
        }
        return 19260817;
    }
    void delate(int x,int to){
        if(tree[x].ch[0])
            delate(tree[x].ch[0],to);
        if(tree[x].ch[1])
            delate(tree[x].ch[1],to);
        bel[tree[x].pos]=to;
        insert(tree[x].val,to,tree[x].pos,x,1);
        return;
    }
    void union_splay(int x,int y){
        int rx=root[x],ry=root[y];
        if(tree[rx].size<tree[ry].size)
            swap(rx,ry);
        delate(ry,bel[tree[rx].pos]);
        return;
    }
}slay;
struct DSU{
    int fa[MAX];
    void init(int n){
        for(int i=1;i<=n;i++)
            fa[i]=i;
        return;
    }
    void father(int x,int y){
        int fx=find(x),fy=find(y);
        fa[fx]=fy;
        return;
    }
    int find(int x){
        if(fa[x]!=x)
            fa[x]=find(fa[x]);
        return fa[x];
    }
}dsu;
int read(){
    char c=getchar();
    int rt=0,f=1;
    while(c<'0'||c>'9'){
        if(f=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rt=rt*10+c-'0';
        c=getchar();
    }
    return rt*f;
}
int rkk[MAX],rtot;
int main(){
    int n=read(),m=read();
    dsu.init(n);
    for(int i=1;i<=n;i++)
        rkk[i]=read();
    for(int i=1;i<=m;i++){
        int a=read(),b=read();
        dsu.father(b,a);
    }
    for(int i=1;i<=n;i++){
        if(dsu.find(i)==i){
            bel[i]=++rtot;
            slay.insert(rkk[i],bel[i],i,0,0);
        }
    }
    for(int i=1;i<=n;i++){
        int fa=dsu.find(i);
        if(fa!=i){
            bel[i]=bel[fa];
            slay.insert(rkk[i],bel[i],i,0,0);
        }
    }
    int t=read();
    while(t--){
        char c=getchar();
        int a=read(),b=read();
        if(c=='Q')
            printf("%d\n",slay.kth(b,bel[a]));
        else{
            slay.union_splay(bel[a],bel[b]);
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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