T1：

　　水题；

 

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define maxn 100005int n,ai[maxn],Max[maxn],bi[maxn],size;int tree[maxn];inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>'9'||Cget<'0') Cget=getchar();    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }}inline void add(int x){    while(x<=n) tree[x]++,x+=x&(-x);}inline bool judge(int l,int r){    int res=0;l--;    while(r) res+=tree[r],r-=r&(-r);    while(l) res-=tree[l],l-=l&(-l);    return res;}int lower_bound(int x){    int l=1,r=size,mid;    while(l<=r)    {        mid=l+r>>1;        if(bi[mid]==x) return mid;        if(bi[mid]
        
         0;i--) Max[i]=max(Max[i+1],ai[i]);        bool ans=true;        add(ai[1]);        for(int i=2;i
        
       
      
     

 

T2：

　　样例不过却ac，我也很无奈啊~~

 

 

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define maxn 1005int x[maxn],y[maxn],bi[maxn<<1],size,n,cnt;int num[maxn<<1][maxn<<1],ans=0;inline void in(int &now){    int if_z=1;now=0;    char Cget=getchar();    while(Cget>'9'||Cget<'0')    {        if(Cget=='-')if_z=-1;        Cget=getchar();    }    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }    now*=if_z;}int dge(int xx,int yy){    int xx_=lower_bound(bi+1,bi+size+1,xx)-bi;    int yy_=lower_bound(bi+1,bi+size+1,yy)-bi;    if(bi[xx_]==xx&&yy==bi[yy_]) return num[xx_][yy_];    return 0;}inline void Count(int a,int b){    int xa=x[a],ya=y[a],xb=x[b],yb=y[b];    num[xa][ya]--,num[xb][yb]--;    if(xa>xb) swap(xa,xb),swap(ya,yb);    int dx=bi[xb]-bi[xa],dy=bi[yb]-bi[ya];    int xxa,yya,xxb,yyb;    xxa=bi[xa]+dy,yya=bi[ya]-dx;    xxb=bi[xb]-dy,yyb=bi[yb]-dx;    if(xxa!=xxb||yya!=yyb) ans+=dge(xxa,yya)*dge(xxb,yyb);    else ans+=dge(xxa,yya)*(dge(xxb,yyb)-1);    xxa=bi[xa]-dy,yya=bi[ya]+dx;    xxb=bi[xb]+dy,yyb=bi[yb]+dx;    if(xxa!=xxb||yya!=yyb) ans+=dge(xxa,yya)*dge(xxb,yyb);    else ans+=dge(xxa,yya)*(dge(xxb,yyb)-1);    num[xa][ya]++,num[xb][yb]++;}int main(){    freopen("car.in","r",stdin);    freopen("car.out","w",stdout);    in(n);    for(int i=1;i<=n;i++)    {        in(x[i]),in(y[i]);        bi[++cnt]=x[i],bi[++cnt]=y[i];    }    sort(bi+1,bi+cnt+1),size=unique(bi+1,bi+cnt+1)-bi-1;    for(int i=1;i<=n;i++)    {        x[i]=lower_bound(bi+1,bi+size+1,x[i])-bi;        y[i]=lower_bound(bi+1,bi+size+1,y[i])-bi;        num[x[i]][y[i]]++;    }    for(int i=1;i<=n;i++)    {        for(int v=i+1;v<=n;v++)        {            if(v==i) continue;            Count(i,v);        }    }    cout<
       
      
     

 

 

T3：

　　坑爹！！！！

 

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define maxn 30005#define ll long longll n,ai[maxn],bi[maxn],size,root[maxn],tot;ll lc[maxn*30],rc[maxn*30],dis[maxn*30],m;inline void in(ll &now){    char Cget=getchar();now=0;    while(Cget>'9'||Cget<'0')Cget=getchar();    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }}void build(ll &now,ll l,ll r){    now=++tot;    if(l==r) return;    ll mid=l+r>>1;    build(lc[now],l,mid);    build(rc[now],mid+1,r);}void add(ll &now,ll pre,ll l,ll r,ll to){    now=++tot;dis[now]=dis[pre]+1;    if(l==r) return;ll mid=l+r>>1;    if(to<=mid) add(lc[now],lc[pre],l,mid,to),rc[now]=rc[pre];    else add(rc[now],rc[pre],mid+1,r,to),lc[now]=lc[pre];}ll query(ll now,ll l,ll r,ll k){    if(l==r) return l;    ll mid=l+r>>1;    if(k<=dis[lc[now]]) return query(lc[now],l,mid,k);    else return query(rc[now],mid+1,r,k-dis[lc[now]]);}int main(){    freopen("rollcall.in","r",stdin);    freopen("rollcall.out","w",stdout);    in(n),in(m);    for(ll i=1;i<=n;i++) in(ai[i]),bi[i]=ai[i];    sort(bi+1,bi+n+1),size=unique(bi+1,bi+n+1)-bi-1;    for(ll i=1;i<=n;i++) ai[i]=lower_bound(bi+1,bi+size+1,ai[i])-bi;    build(root[0],1,size);    for(ll i=1;i<=n;i++) add(root[i],root[i-1],1,size,ai[i]);    ll pos;    for(ll i=1;i<=m;i++) in(pos),printf("%I64d\n",bi[query(root[pos],1,size,i)]);    return 0;}