【贪心】CF1779 D

r囧r小猫 2024-03-23 23:20 86阅读 0赞

**不会1700**

[Problem - 1779D - Codeforces][]

题意：

![2812e830d8fc42acaa190aa13f186e7a.png][]

![af18f28586c14dbea1d95cf0eb31ff9a.png][]

思路：

首先手推样例，可以发现一些零碎的性质：

![af74f263db0d477cb6fbfd856454af6b.jpeg][]

然后考虑如何去计算贡献

难点在于，当一个区间的两端是区间max时，怎么去计算贡献

事实上，只需要考虑这个数上次出现的最近位置即可

用pre数组记录这个数上次出现的最近位置，用st表判断是否为区间max

如果是，就统计这个元素需要被染色次数，然后比较颜料是否足够即可

还有一点细节就是，不能漏统计最后一段

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 998244353;
    
    int n;
    int a[N], b[N], c[N];
    int f[N][33];
    
    void F_init() {
    	for (int i = 1; i <= n; i ++) {
    		f[i][0] = b[i];
    	}
    
    	for (int j = 1; j <= 30; j ++) {
    		for (int i = 1; i + (1 << (j - 1)) <= n; i ++) {
    			f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    		}
    	}
    }
    int query_mx(int l, int r) {
    	int k = r - l + 1;
    	int lg = std::log2(k);
    	return std::max(f[l][lg], f[r - (1 << lg) + 1][lg]);
    }
    void solve() {
    	std::cin >> n;
    
    	for (int i = 1; i <= n; i ++) {
    		a[i] = b[i] = c[i] = 0;
    		for (int j = 0; j <= 30; j ++) {
    			f[i][j] = 0;
    		}
    	}
    	for (int i = 1; i <= n; i ++) {
    		std::cin >> a[i];
    	}
    	
    	for (int i = 1; i <= n; i ++) {
    		std::cin >> b[i];
    	}
    
    	std::map<int,int> mp, mp2, pre;
    
    	int m;
    	std::cin >> m;
    
    	for (int i = 1; i <= m; i ++) {
    		std::cin >> c[i];
    		mp[c[i]] ++;
    	}
    
    	for (int i = 1; i <= n; i ++) {
    		if (b[i] > a[i]) {
    			std::cout << "NO" << "\n";
    			return;
    		}
    	}
    
    	F_init();
    
    	for (int i = 1; i <= n; i ++) {
    		if (a[i] == b[i]) continue;
    		if (!pre[b[i]]) {
    			pre[b[i]] = i;
    			continue;
    		}
    		if (query_mx(pre[b[i]], i) > b[i]) {
    			mp2[b[i]] ++;
    		}
    		pre[b[i]] = i;
    	}
    	for (auto v : pre) {
    		if (v.second) {
    			mp2[v.first] ++;
    		}
    	}
    	for (auto v : mp2) {
    		if (v.second > mp[v.first]) {
    			std::cout << "NO" << "\n";
    			return;
    		}
    	}
    
    	std::cout << "YES" << "\n";
    }
    
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        std::cin >> t;
        
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - 1779D - Codeforces]: https://codeforces.com/problemset/problem/1779/D
[2812e830d8fc42acaa190aa13f186e7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/32f1364365f54466812d7bb5a36b7d3d.png
[af18f28586c14dbea1d95cf0eb31ff9a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9120f7c5259d4653a06d1298f384a15d.png
[af74f263db0d477cb6fbfd856454af6b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d259cd09153546e2a5847d26d9d0d5b8.png