1546: 数牌Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 31 Solved: 6[Submit][Status][Web Board]Description从西安到杭州的火车实在是太漫长了，为了打发时间，zjc买了n张扑克牌 （一张一张卖的你们没见过吧▽）牌的位置为1,2,3,…,n ，牌面大小为 3….,9,10,J,Q,K,A,2，牌的花色有a,b,c,d 分别表示红桃、黑桃、方块、梅花。如a9 表示红桃9，d2表示梅花2 。现在有m个操作：1 x y 表示交换位置为x和位置为y的牌2 k pq 表示询问第k张花色为p，牌面为q的位置(pq为一个字符串，如a9，d2等)Input输入多组数据第一行输入一个n (1<=n<=100000)表示zjc买了n张牌第二行输入n张牌， 扑克牌用pq表示，p为牌的花色，q为牌的牌面，p为a,b,c,d，q为3….,9,10,J,Q,K,A,2。第i 张牌的位置为i (1<=i<=n)。第三行输入一个数m(1<=m<=100000) 表示有m次询问接下来m行每行输入一个整数op（1或者2）op=1，输入 x ,y ，（1<=x,y<=n），交换位置为x的牌和位置为y的牌op=2, 输入k, pq，(1<=k<=n)询问第k张花色为p，牌面大小为q的牌的位置，对于每个询问，输出对应位置，如果牌不存在，，则输出-1Output对于每个询问，输出牌对应的位置，如果牌不存在，则输出-1Sample Input5a3 b9 b9 cJ d251 1 32 1 b91 2 52 2 b92 2 a3Sample Output15
-1
//线段树的节点存储N张的数组即可每个节点的数组对应的牌保存他左右儿子的此牌的数量和
#include<bits/stdc++.h>using namespace std;const int maxn=100111;const int inf=999999999;#define lson (rt<<1),L,M#define rson (rt<<1|1),M+1,R#define M ((L+R)>>1)#define For(i,n) for(int i=0;i<(n);i++)template<class T>inline T read(T&x){char c;while((c=getchar())<=32);bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return x;}template<class T> inline void read_(T&x,T&y){read(x);read(y);}template<class T> inline void write(T x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}template<class T>inline void writeln(T x){write(x);putchar('\n');}// ——-IO template——struct node{int kind[54];node(){memset(kind,0,sizeof(kind));}}p[maxn<<2];int a[maxn];int getid(){int x=0;char tmp[2];scanf("%s",tmp);x=(tmp[0]-'a')*10;if(tmp[1]>='0'&&tmp[1]<='9')x+=tmp[1]-'0';elsex+=tmp[1]-'J'+11;return x;}void update(int rt,int L,int R,int i,int ax,int v){if(L==R){p[rt].kind[ax]+=v;// printf("%d %d %d %d %d %d\n",rt,L,R,i,ax,p[rt].kind[ax]);return ;}if(i<=M)update(lson,i,ax,v);elseupdate(rson,i,ax,v);p[rt].kind[ax]=p[rt<<1].kind[ax]+p[rt<<1|1].kind[ax];}int query(int rt,int L,int R,int x,int y){if(L==R){return R;}if(p[rt<<1].kind[y]<x)return query(rson,x-p[rt<<1].kind[y],y);elsereturn query(lson,x,y);}int main(){//freopen("in.txt","r",stdin);int n,m,i,j,k,t;while(~scanf("%d",&n)){for(i=1;i<=n;i++){a[i]=getid();update(1,1,n,i,a[i],1);//writeln(a[i]);}//for(i=1;i<=1;i++)//{//for(j=0;j<54;j++)//if(p[i].kind[j])printf("**%d",p[i].kind[j]);//printf(")\n");//}read(m);while(m–){int op;int x;read_(op,x);if(op==1){int y;read(y);if(x==y)continue;// cout<<"====="<<endl;update(1,1,n,x,a[x],-1);update(1,1,n,y,a[x],1);update(1,1,n,x,a[y],1);update(1,1,n,y,a[y],-1);swap(a[x],a[y]);}else{int y=getid();// writeln(y);// printf("—%d\n",p[1].kind[y]);if(p[1].kind[y]<x){writeln(-1);}else{writeln(query(1,1,n,x,y));}}}}return 0;}
如果你曾歌颂黎明，那么也请你拥抱黑夜
