codeforces round 977 (div.2) C2(访问set的第一个元素，观察数据规律-出现次序,用set记录数字第一次出现的位置)

cavendishboys / 2024-10-14 / 原文

解题历程：

我首先想到的是等效法，每一次操作可以等效为每次将第一个人抽出放入一组，后面的人往前移，而该组的人就是可以任意放置的人，当b中后面再出现与前一个相同的人时，就不进行操作，当b中出现不同的人时，就看看这组中有没有这个人，有的话就下一个循环，没有的话就看看这个新的人是否按a中的顺序出现，若是没有就是NO，否则将这个人放入那个组中，一直到最后都没问题，那结果就是YES，而这个组可以用长度为n的数组存储，1表示出现过，0表示没出现过。

正确思路：

若是C1的情况，则只需要将b中数第一次出现的位置记录下来即可，再看看他们是不是按照a的顺序出现，若是是的话就是YES，否则就是NO，如果是C2的情况，需要更改数组b的值，那么就需要将b中的所有数出现的位置记录下来，因为改变一个数后，原本第二次出现的数可能变成第一次出现，所以可以用set容器记录数出现的所有位置，set还会自动排序，set中的第一个数就是该数第一次出现的位置，那么每次更改的时候就只需要删除原数的set中的位置，再在新数的set中加入该位置即可，然后根据a的顺序查找他们第一次出现的位置是否是单调递增的，在这个过程中有一个技巧，就是用一个变量flag来记录状态，若是出现一次递减的话就让其加1，若是去掉一个数，则可以减去该数对flag的影响，若是加上一个数，则可以加上该数对flag的影响，这是一个微观的处理思想，因为改变一个数只会对两边的增减会有影响

代码：

#include<bits/stdc++.h>
 
using namespace std;

void solve() {
	int n,m,q;
	cin>>n>>m>>q;
	vector<int>a(n+1);
	vector<int>pos(n+1);//为了确定a的前后是谁 
	vector<int>b(m+1);
	vector<set<int>>s(n+1);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		pos[a[i]]=i;
		s[a[i]].insert(m+1);
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
		s[b[i]].insert(i);
	}
	vector<int>fis(n+1);
	for(int i=1;i<=n;i++){
		fis[i]=*s[i].begin();
	}
	int flag=0;
	for(int i=2;i<=n;i++){
		if(fis[a[i-1]]>fis[a[i]])flag++;
	}
	if(!flag)cout<<"YA"<<endl;
	else cout<<"TIDAK"<<endl;
	auto update=[&](int i){
		if(i>1)
		flag-=fis[a[i-1]]>fis[a[i]];
		if(i<n)
		flag-=fis[a[i]]>fis[a[i+1]];
		fis[a[i]]=*s[a[i]].begin();
		if(i>1)
		flag+=fis[a[i-1]]>fis[a[i]];
		if(i<n)
		flag+=fis[a[i]]>fis[a[i+1]];
	};
	while(q--){
		int v,d,old;
		cin>>v>>d;
		old=b[v];
		b[v]=d;
		s[old].erase(v);
		s[d].insert(v);
		update(pos[old]);
		update(pos[d]);
		if(!flag)cout<<"YA"<<endl;
		else cout<<"TIDAK"<<endl;
	}
}

int main(void )
{   
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    int test=1;
    cin>>test;
	
    while(test--)
    {
    	solve();
	}
        
    return 0;
}

反思：