E. Nezzar and Binary String（逆向思维+线段树）

- 日理万妓 2021-07-16 14:33 360阅读 0赞

[题目][Link 1]

思路：从逆向想一下，发现最后得到的一定是最后的字符串f，然后往前推，因为只能改变<len/2的元素，不难发现改变已经定下来了，即只能全改为数量大的那个字符，如果长度为偶数两种字符相等则不能达成。维护和查找用线段树覆盖。

down的一个修改  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]  
Code:

#include<iostream>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    typedef long long ll;
    using namespace std;
    
    struct node
    { 
    	ll l, r, f, w;
    }tree[5000005];
    
    inline void build(int k, int ll, int rr)
    { 
    	tree[k].l = ll, tree[k].r = rr, tree[k].f = -1;
    	if (tree[k].l == tree[k].r) {  char ch;cin >> ch;tree[k].w=ch-'0'; return; }
    	int mid = (tree[k].l + tree[k].r) / 2;
    	build(2 * k, ll, mid);
    	build(2 * k + 1, mid + 1, rr);
    	tree[k].w = tree[2 * k].w + tree[2 * k + 1].w;
    }
    
    inline void down(int k)
    { 
    	if (tree[k].f == -1)return;//表示此时f为无效状态
    	tree[2 * k].f = tree[k].f;
    	tree[2 * k + 1].f = tree[k].f;
    	tree[2 * k].w = tree[k].f * (tree[2 * k].r - tree[2 * k].l + 1);//直接让后面的值等于f
    	tree[2 * k + 1].w = tree[k].f * (tree[2 * k + 1].r - tree[2 * k + 1].l + 1);
    	tree[k].f = -1;//给儿子赋值后再变为无效状态
    }
    
    inline ll ask_interval(int k, int x, int y)
    { 
    	ll ans = 0;
    	if (x <= tree[k].l && y >= tree[k].r)
    	{ 
    		return tree[k].w;
    	}
    	down(k);
    	int mid = (tree[k].l + tree[k].r) / 2;
    	if (x <= mid)ans += ask_interval(2 * k, x, y);
    	if (y > mid)ans += ask_interval(2 * k + 1, x, y);
    	return ans;
    }
    
    inline void change_interval(int k, int x, int y, int add)
    { 
    	if (x <= tree[k].l && y >= tree[k].r)
    	{ 
    		tree[k].w = add * (tree[k].r - tree[k].l + 1);
    		tree[k].f = add;
    		return;
    	}
    	down(k);
    	int mid = (tree[k].l + tree[k].r) / 2;
    	if (x <= mid)change_interval(2 * k, x, y, add);
    	if (y > mid)change_interval(2 * k + 1, x, y, add);
    	tree[k].w = tree[2 * k].w + tree[2 * k + 1].w;
    }
    const int Max = 1e6 + 5;
    int a[Max], b[Max], q[Max][2];
    
    int main()
    { 
    	FAST;
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, qq;cin >> n >> qq;
    		for (int i = 1;i <= n;i++)
    		{ 
    			char c;cin >> c;
    			a[i] = c - '0';
    		}
    		build(1, 1, n);
    		for (int i = 1;i <= qq;i++)cin >> q[i][0] >> q[i][1];
    		int f = 1;
    		for (int i = qq;i >=1 ;i--)
    		{ 
    			int l = q[i][0], r = q[i][1];
    			int sum = ask_interval(1, l, r);
    			if ((r - l+1) % 2 == 0 && sum == (r - l + 1) / 2) { 
    				f = 0;
    			}
    			if (sum <= (r - l + 1) / 2)change_interval(1, l, r, 0);
    			else change_interval(1, l, r, 1);
    		}
    		for (int i = 1;i <= n;i++)
    		{ 
    			int g = ask_interval(1, i, i);
    			if (a[i] != g)f = 0;
    		}
    		if (f)cout << "YES" << endl;
    		else cout << "NO" << endl;
    	}
    	
    }

[Link 1]: https://codeforc.es/contest/1478/problem/E
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/09c1a3c4641047e3bf2d26fe5155ac2f.png