记录编号	561104	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	Giving slaps(题目有误)	最终得分	100
用户昵称	Sicly	是否通过	通过
代码语言	C++	运行时间	0.254 s
提交时间	2021-06-20 16:36:44	内存使用	5.13 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n,k,m,q;
int b[10010];
const int INF=1e15;
 typedef struct
{
    int to;
    int val;
}Point;
vector<Point> map[100020];
int dis[10020];
int path[10020];
int c;
 
/**/const int maxn=20005;
const int V=10000;
struct node
{
	int l,r,sum;
	node()
	{
		l=r=sum=0;
	}
}tree[maxn<<2];
 
void pushup(int i)
{
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
	return;
}
void update(int i,int l,int r,int pos,int val)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)
	{
		tree[i].sum+=val;
		return ;
	}
	int mid=l + r >> 1;
	if(pos <= mid)update(i << 1,l,mid,pos,val);
	else update(i << 1 | 1,mid+1,r,pos,val);
	pushup(i);
	return ;
}
int query(int i,int k)
{
	if(tree[i].l==tree[i].r)return tree[i].l;
	int x=tree[i<<1].sum;
	int mid=tree[i].l+tree[i].r>>1;
	if(k<=x)return query(i<<1,k);
	else return query(i<<1|1,k-x); 
}
void SPFA()
{
    for(int i=2;i<=n;i++)
        dis[i]=INF;
    dis[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<map[u].size();i++)
        {
            Point v=map[u][i];
            if(dis[v.to]>dis[u]+v.val)
            {
                dis[v.to]=dis[u]+v.val;
                path[v.to]=u; //存每个点的前一个点
                q.push(v.to);
            }
        }
    }
}
 
int main()
{
	freopen("LPH_girlsonwayhome.in","r",stdin);//real one 
    freopen("LPH_girlsonwayhome.out","w",stdout);
    cin>>n>>k>>m>>q>>c;
    for(int i=1;i<=n;i++)
    {
    	cin>>b[i];
	}
    memset(path,0,sizeof(path));
    for(int i=0;i<=n;i++)
    {
       	map[i].clear();
	}
    for(int i=1;i<=m;i++)
    {
        int u,v,e;//u到v有一条有向边，权值为e
        cin>>u>>v>>e;
        /*cout<<u<<' '<<v<<' '<<e<<endl;
        Sleep(1000);*/
        Point s;
        s.to=v;
        s.val=e;
        map[u].push_back(s);
		Point si;
        si.to=u;
        si.val=e;
        map[v].push_back(si);
    }
    SPFA();
    int num[10020];
    int cnt=0;
    //起始都是从1开始出发
    for(int i=c;i!=1;i=path[i])
    {
        num[cnt++]=i;
    /*cout<<i<<endl<<endl;
        Sleep(1000);*/ 
    }
    for(int i=cnt-1;i>=0;i--)
    {
        update(1,1,V,b[num[i]],1);
       	//cout<<b[num[i]]<<endl; 
    }
    update(1,1,V,b[1],1);
    /*for(int i=1;i<=n;i++)
    {
    	if(tree[i].l==tree[i].r)cout<<i<<' '<<tree[i].l<<endl;
    	Sleep(500);
	}*/
	for(int i=1;i<=q;i++)
	{
		int x;
		char s[10];
		cin>>s;
		if(s[0]=='C')
		{
			cin>>x;
			int d;
			cin>>d;
			update(1,1,V,b[x],-1);
			update(1,1,V,b[x]=d,1);
		}
		else
		{
			cout<<query(1,k)<<endl;
		}
	}
    return 0;
 }