这题最不好求的一部分是rank部分 因为top每次都是把一个数放在队头 不会穿插在数组里 也就是说后面没有top过的一部分数 依旧保持有序
这样可以分为两部分来处理 比如 1 2 3 4 5 6 7 TOP 3 TOP 5 TOP 7后 会是这么一种状态 7 5 3 1 2 4 6 这样可以建立两颗线段树一个处理前面一个处理后面
对于N 值很大 肯定是需要离散化的 前面的那颗就可以用普通的求第k大 标记 求和来求出第几 以及x在哪个位置 后面的线段树的值 可以这么来表示 s[w] = num[i]-num[i-1]
这样对于询问rank x 就用线段树找第一个大于等于x的数。
虽然错了很多次，看见那个红红的AC还是很高兴的。。。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 #include<map> 11 using namespace std; 12 #define N 100010 13 #define LL long long 14 #define INF 0xfffffff 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 struct node 19 { 20 char s[10]; 21 int d; 22 }p[N]; 23 int s[N<<2],o[N<<2],ss[N<<2],oo[N<<2]; 24 int po[N],fo[N],a[N]; 25 bool vis[N]; 26 map<int,int>f; 27 void up(int w) 28 { 29 s[w] = s[w<<1]+s[w<<1|1]; 30 } 31 void up1(int w) 32 { 33 ss[w] = ss[w<<1]+ss[w<<1|1]; 34 oo[w] = oo[w<<1]+oo[w<<1|1]; 35 } 36 void build(int l,int r,int w) 37 { 38 if(l==r) 39 { 40 s[w] = oo[w] = 0; 41 if(fo[l]>fo[l-1]) 42 ss[w] = fo[l]-fo[l-1]; 43 return ; 44 } 45 int m= (l+r)>>1; 46 build(l,m,w<<1); 47 build(m+1,r,w<<1|1); 48 up(w); 49 up1(w); 50 } 51 52 void update(int pos,int k,int d,int l,int r,int w) 53 { 54 if(l==r) 55 { 56 s[w] = d; 57 if(d) 58 { 59 po[k] = l; 60 o[w] = fo[k]; 61 // cout<<k<<" "<<fo[k]<<endl; 62 63 } 64 return ; 65 } 66 int m = (l+r)>>1; 67 if(pos>m) update(pos,k,d,m+1,r,w<<1|1); 68 else update(pos,k,d,l,m,w<<1); 69 up(w); 70 } 71 void update1(int k,int l,int r,int w) 72 { 73 if(l==r) 74 { 75 ss[w]--; 76 oo[w] = 1; 77 return ; 78 } 79 int m = (l+r)>>1; 80 if(k>m) update1(k,m+1,r,w<<1|1); 81 else update1(k,l,m,w<<1); 82 up1(w); 83 } 84 int query(int p,int l,int r,int w) 85 { 86 if(l==r) 87 { 88 return o[w]; 89 } 90 int m = (l+r)>>1; 91 if(p>s[w<<1]) return query(p-s[w<<1],m+1,r,w<<1|1); 92 else return query(p,l,m,w<<1); 93 } 94 int query1(int p,int l,int r,int w) 95 {//cout<<l<<" "<<r<<" "<<ss[w]<<" "<<p<<endl; 96 if(l==r) 97 { 98 //cout<<l<<endl; 99 if(vis[l]) 100 return fo[l]-1-(ss[w]-p); 101 else 102 return fo[l]-(ss[w]-p); 103 } 104 int m = (l+r)>>1; 105 if(p<=ss[w<<1]) 106 return query1(p,l,m,w<<1); 107 else 108 return query1(p-ss[w<<1],m+1,r,w<<1|1); 109 } 110 int getsum(int a,int b,int l,int r,int w) 111 { 112 if(a<=l&&b>=r) 113 return s[w]; 114 int m = (l+r)>>1; 115 int re = 0; 116 if(a<=m) 117 re+=getsum(a,b,l,m,w<<1); 118 if(b>m) 119 re+=getsum(a,b,m+1,r,w<<1|1); 120 return re; 121 } 122 int getsum1(int a,int b,int l,int r,int w) 123 { 124 if(a<=l&&b>=r) 125 return oo[w]; 126 int m = (l+r)>>1; 127 int re = 0; 128 if(a<=m) 129 re+=getsum1(a,b,l,m,w<<1); 130 if(b>m) 131 re+=getsum1(a,b,m+1,r,w<<1|1); 132 return re; 133 } 134 int main() 135 { 136 int i,n,q,kk=0,t; 137 cin>>t; 138 while(t--) 139 { 140 memset(vis,0,sizeof(vis)); 141 memset(fo,0,sizeof(fo)); 142 memset(o,0,sizeof(o)); 143 f.clear(); 144 scanf("%d%d",&n,&q); 145 for(i = 0 ; i < q; i++) 146 { 147 scanf("%s%d",p[i].s,&p[i].d); 148 a[i] = p[i].d; 149 } 150 sort(a,a+q); 151 int g = 0; 152 for(i = 0;i < q ;i++) 153 { 154 if(!f[a[i]]) 155 { 156 g++; 157 f[a[i]] = g; 158 fo[g] = a[i]; 159 //cout<<g<<" "<<a[i]<<endl; 160 } 161 } 162 g++; 163 f[n+1] = g; 164 fo[g] = n+1; 165 g = q+1; 166 build(1,g,1); 167 int e = g+1; 168 printf("Case %d: ",++kk); 169 for(i = 0 ; i < q ; i++) 170 { 171 int k = f[p[i].d]; 172 if(strcmp(p[i].s,"Top")==0) 173 { 174 e--; 175 if(vis[k]) 176 update(po[k],k,0,1,g,1); 177 else 178 update1(k,1,g,1); 179 update(e,k,1,1,g,1); 180 vis[k]= 1; 181 } 182 else if(strcmp(p[i].s,"Rank")==0) 183 { 184 //int sum = getsum(1,g,1,g,1); 185 //cout<<s[1]<<endl; 186 //cout<<getsum1(1,2,1,g,1)<<endl; 187 if(p[i].d>s[1]) 188 { 189 int cnt = query1(p[i].d-s[1],1,g,1); 190 printf("%d ",cnt); 191 } 192 else 193 { 194 printf("%d ",query(p[i].d,1,g,1)); 195 } 196 } 197 else 198 { 199 if(vis[k]) 200 { 201 int cnt = getsum(1,po[k],1,g,1); 202 //cout<<po[k]<<endl; 203 printf("%d ",cnt); 204 } 205 else 206 { 207 if(k==g) 208 cout<<p[i].d<<endl; 209 else 210 { 211 int cnt = getsum1(k+1,g,1,g,1); 212 printf("%d ",cnt+p[i].d); 213 } 214 } 215 } 216 } 217 } 218 return 0; 219 }