L2-2又见火车入栈

StarrySky 最近沉迷的精灵宝可梦即将增加两张新地图：铠之孤岛，冠之雪原。

为了迎接新世界的到来，StarrySky 整天守在木杆镇的车站等待着通往新区域的火车。

为了消磨时间，StarrySky 依次记录下了一天当中火车进站、出站的情况。根据观察发现，木杆镇的火车站与 IvyHole 的算法世界中的“栈”有着异曲同工之妙，即：标号为 i 的火车进站之后，如果后续有标号为 j 的火车进站，则 i 这列火车不可能在 j 这列火车之前出站，再用四个字简单概括一下就是：先进后出。

在 StarrySky 的记录中，in 表示有火车进站，out 表示有火车出站，且所有记录全都合法，即：当火车站内没有火车时，不可能出现 out 记录，但是在所有记录结束时，车站内有可能依旧停留有火车。

为了方便表示，根据进站顺序给每列火车唯一标号，例如：第一个 in 表示标号为 1 的火车进站，第二个 in 表示标号为 2 的火车进站，此时如果有 out 记录，则表示标号为 2 的火车出站，出站后火车站内只剩下标号为 1 的火车，...，以此类推处理火车记录，就可以得知一整天的火车进出站情况。

为了考验 IvyHole 的能力，在上述记录的基础上，StarrySky 提出了询问，在处理完第 x 条记录后，火车站内剩余的火车中，第 y 个进入火车站的火车编号是多少？StarrySky 保证了询问一定合法，即：如果第 x 条记录后火车站内只剩下了 k 辆火车，则 k > 0 且 $y \leq k$ .

由于 IvyHole 近期忙于 OJ 平台的维护，所以将这个问题抛给了你，希望你代替 IvyHole 回答 StarrySky 的问题。

第一行输入一个正整数 n，表示这一天内 StarrySky 记录的数目。
接下去 n 行，每行一个火车进出站的记录，即：每行输入 in 或者 out 表示火车进出站情况，且记录一定合法。
第 n + 2 行一个正整数 q，表示 StarrySky 的询问次数。
接下去 q 行，每行两个正整数 x, y，表示询问在处理完第 x 条记录后，火车站内剩余的火车中，第 y 个进入火车站的火车编号是多少？保证询问一定合法。

#include<bits/stdc++.h> using namespace std; struct node{ int l,r; int id; }a[1<<20]; int ans[1<<20]; int vis[1<<20]; int sta[1<<20],tot=1; bool cmp(node x,node y){ return x.l<y.l; } char s[15]; int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); if(s[0]=='i') vis[i]=1; } int q;scanf("%d",&q); for(int i=1;i<=q;i++){ int x,y;scanf("%d%d",&x,&y); a[i]={x,y,i}; } sort(a+1,a+1+q,cmp); int k=0,num=1; for(int i=1;i<=q;i++){ while(a[i].l!=k){ if(vis[++k]) sta[tot++]=num++; else tot--; } ans[a[i].id]=sta[a[i].r]; } for(int i=1;i<=q;i++) printf("%d\n",ans[i]); return 0; }

#include<bits/stdc++.h> using namespace std; struct node { int x,y,id; }Q[1000005]; bool cmp(node a,node b) { return a.x<b.x; } int t=0,S[1000005],ans[1000005]; char R[1000005][5]; int main() { int i,j,k=1,n,q; scanf("%d",&n); for(i=0;i<n;i++)scanf("%s",R[i]); scanf("%d",&q); for(i=0;i<q;i++)scanf("%d%d",&Q[i].x,&Q[i].y),Q[i].id=i; sort(Q,Q+q,cmp); for(i=j=0;i<q;i++) { for(;j<n&&j<=Q[i].x-1;j++) { if(R[j][0]=='i')S[++t]=k++; else t--; } ans[Q[i].id]=S[Q[i].y]; } for(i=0;i<q;i++)printf("%d\n",ans[i]); return 0; }

详情