题目链接:这里
题意:T组数据,每组给定一个n一个m,在给定两个长度为n的数组a和b,再给定m次操作,每次给定l和r,每次可以把[l,r]的数进行任意调换位置,问能否在转换后使得a数组变成b数组。
解法:贪心,用结构体存储a数组,一共两个域,一个是值,一个是下标,这个下标指的是他最后应该在的位置即这个值在b数组中的下标。随后m次操作可以看做是对a数组的lr这个区间进行m次sort,sort是根据下标从小到大排序,这样会使得这个数向他应该在的位置偏移,就是把a数组往b数组上靠,该向左的向左去,该向右的向右去,如果最后的时候都偏移到了自己应该在的位置就是Yes,否则就是No。复杂度O(max((n*n),(m*n*log(n))))。

//HDU 5821

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, id;
    node(){}
    node(int x, int id) : x(x), id(id) {}
    bool operator < (const node &rhs) const{
        return id < rhs.id;
    }
}a[1005];
int b[1005];
int main()
{
    int T, n, m;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i].x);
            a[i].id = -1;
        }
        for(int i = 0; i < n; i++){
            scanf("%d", &b[i]);
            for(int j = 0; j < n; j++){
                if(a[j].x == b[i] && a[j].id == -1){
                    a[j].id = i;
                    break;
                }
            }
        }
        while(m--){
            int l, r;
            scanf("%d%d", &l, &r);
            sort(a+l-1, a+r);
        }
        bool flag = 1;
        for(int i = 0; i < n; i++){
            if(a[i].x != b[i]){
                flag = 0;
                break;
            }
        }
        puts(flag?"Yes":"No");
    }
    return 0;
}