自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:17:50，当前版本为作者最后更新于2025-07-10 09:51:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

秒了，但是目前最劣解，但是目前最短解。

每个限制关系只限制了两种数字的相对位置关系，于是考虑对于每个限制进行 check，这个是好做的。

具体的，我们可以统计每一个位置前某个数字的数量，然后对于限制 $(x,y)$，我们将两个数列中对应 $x$ 前面的 $y$ 数量进行比对即可。

一个很好想的维护思路是前缀和，但是 MLE 了。

于是可以存位置，查找的时候二分即可。

时间复杂度 $O(nm\log n)$。

我们对于 $(x,y)$ 做一个类似于启发式合并的优化，这样就有了 $O(m\frac{n}{k}\log n)$。

另外的数据范围其实应该是 $m\le \frac{k(k-1)}{2}$，代进去复杂度应为 $O(nk\log n)$，喜提最劣解。

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
vector<int>v1[1005];
vector<int>v2[1005];
pair<int,int>p[50005];
int main(){
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=1;i<=m;i++)
    cin>>p[i].first>>p[i].second;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v1[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        v2[b[i]].push_back(i);
    }
    for(int i=1;i<=k;i++)
    if(v1[i].size()!=v2[i].size()){
        puts("NIE");
        return 0;
    }
    for(int i=1;i<=m;i++){
        int x=p[i].first,y=p[i].second;
        if(v1[x].size()>v1[y].size())swap(x,y);
        for(int j=0;j<v1[x].size();j++)
        if((lower_bound(v1[y].begin(),v1[y].end(),v1[x][j])-v1[y].begin())!=
          (lower_bound(v2[y].begin(),v2[y].end(),v2[x][j])-v2[y].begin())){
            puts("NIE");
            return 0;
        }
    }
    puts("TAK");
    return 0;
}