免费的平面设计网站,有关电子商务网站建设的论文,搜狗seo查询,校园网站的建设作用正题
题目链接#xff1a;https://www.luogu.org/problemnew/show/P1383 大意
三个操作 T c#xff1a;加入一个字符c U x#xff1a;撤销前x次操作#xff08;只包括T和U#xff09; Q x#xff1a;询问当前第x个字符 解题思路 对于50%的数据U不会撤销到U 所以我们可…正题
题目链接https://www.luogu.org/problemnew/show/P1383 大意
三个操作 T c加入一个字符c U x撤销前x次操作只包括T和U Q x询问当前第x个字符 解题思路 对于50%的数据U不会撤销到U 所以我们可以直接暴力
#includecstdio
#includeiostream
using namespace std;
int n,x,w;
char c,a[100001];
int main()
{scanf(%d\n,n);for (int i1;in;i){cinc;if (cU){scanf(%d,x);w-x;}else if (cQ){scanf(%d,x);printf(%c\n,a[x]);}else{cinc;a[w]c;}}
}
然后正题——撤销撤销 你知道吗它的撤销可以撤销撤销 它还可以撤销撤销撤销 还可以撤销撤销撤销撤销 …… 好了这道题支持离线算法所以我们就用离线算法。 离线算法我们要先构一颗树我们发现如果是TTT操作的话可以直接和下一个版本相连然后加一个字母，如果是U#xA0;#xA0;x" role="presentation" style="position: relative;">UxUxU\ \ x操作的话那么版本xxx就等于版本x#x2212;k#x2212;1" role="presentation" style="position: relative;">x−k−1x−k−1x-k-1所以我们连边 然后用欧拉序来求所有的版本时间负责度O(n)O(n)O(n) 代码
#includecstdio
#includeiostream
#includevector
#define MN 100011
using namespace std;
vectorint q[MN1];//vertor库储存询问
struct node{int to,next,w;
}a[MN1];
int p,x,k,tot,ls[MN1],n,ans[MN1];
char c,st[MN1],s[MN1];
void addl(int x,int y)//连边
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(int x,int sto)//欧拉序求答案
{for(int ils[x];i;ia[i].next)dfs(a[i].to,sto);//自己搜索连接的版本if (s[x]) st[sto]s[x],dfs(x1,sto1);//直接接到下一个版本for (int i0;iq[x].size();i)ans[q[x][i]]st[ans[q[x][i]]];//计算答案
}
int main()
{scanf(%d\n,n);for (int i1;in;i){cinc;if (cT){cins[k];//标记操作}else if (cQ){scanf(%d,x);q[k].push_back(p);//记录询问ans[p]x;}else if (cU){k;scanf(%d,x);addl(k-x-1,k);//连边}}dfs(0,1);//求答案for (int i1;ip;i)if (ans[i]) printf(%c\n,ans[i]);//原序输出
}
