转自：http://blog.csdn.net/xuanandting/article/details/50528582
题意：
大概意思为给出一字符串，然后有两种操作，在某个位置后面插入某个字符，查询更新后字符串中某个位置的字符。
思路：
先倒序处理插入，然后正序处理查询，用线段树去更新和维护区间和，这样就可以了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define lson u<<1,l,m
#define rson u<<1|1,m+1,r
const int maxn=1e6+2010;
int sum[maxn<<2];
void pushup(int u)
{
sum[u]=sum[u<<1]+sum[u<<1|1];
}
void build(int u,int l,int r)
{
if(l==r)
{
sum[u]=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(u);
}
void update(int u,int l,int r,int pos,int x)
{
if(l==r)
{
sum[u]=x;
return;
}
int m=(l+r)>>1;
if(pos<=m)
update(lson,pos,x);
if(pos>m)
update(rson,pos,x);
pushup(u);
}
int query(int u,int l,int r,int val)
{
if(l==r)
return l;
int m=(l+r)>>1;
if(val<=sum[u<<1])
return query(lson,val);
if(val>sum[u<<1])
return query(rson,val-sum[u<<1]);
}
char str[maxn],str1[maxn],cmd[2010],val[2010];
int cnt[2010],pos[maxn],tpos[maxn];
int main()
{
int n,q,len;
scanf("%s",str);
len=strlen(str);
scanf("%d",&q);
cnt[0]=len;
for(int i=1;i<=q;i++)
{
scanf(" %c",&cmd[i]);
if(cmd[i]=='I')
{
scanf(" %c%d",&val[i],&pos[i]);
cnt[i]=cnt[i-1]+1;
}
else
{
scanf("%d",&pos[i]);
cnt[i]=cnt[i-1];
}
}
n=cnt[q];
build(1,1,n);
for(int i=q;i>=1;i--)
{
if(cmd[i]=='I')
{
pos[i]=min(pos[i],cnt[i]);
tpos[i]=query(1,1,n,pos[i]);
update(1,1,n,tpos[i],0);
str1[tpos[i]]=val[i];
}
}
for(int i=1,cnt1=0;i<=n;i++)
{
if(str1[i]==0)
{
str1[i]=str[cnt1++];
}
}
for(int i=1;i<=q;i++)
{
if(cmd[i]=='Q')
{
int ans=query(1,1,n,pos[i]);
printf("%c\n",str1[ans]);
}
else
{
update(1,1,n,tpos[i],1);
}
}
return 0;
}
You are given a string and supposed to do some string manipulations.
Input
The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000.
The second line contains the number of manipulation commands N (0 < N ≤ 2,000). The following N lines describe a command each. The commands are in one of the two formats below:
I ch p: Insert a character ch before the p-th character of the current string. If p is larger than the length of the string, the character is appended to the end of the string.Q p: Query the p-th character of the current string. The input ensures that thep-th character exists.
All characters in the input are digits or lowercase letters of the English alphabet.
Output
For each Q command output one line containing only the single character queried.
Sample Input
ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3
Sample Output
a
d
e
转载请注明原文地址: https://ju.6miu.com/read-7747.html
