Professor Higashikata

Created by LXC on Mon Feb 5 17:03:49 2024

https://codeforces.com/problemset/problem/1847/D

ranting: 1900

tag: data structures, dsu, greedy, implementation, strings

problem

给出一个长度为 $n$ 的字符串 $s$，字符串仅由 0 或 1 构成。

给出 $m$ 个区间 $[l_i,r_i]$ ($1\le i\le m$,$1\le l_i\le r_i\le n$)，你需要将字符串 $s$ 的子段 $[l_i,r_i]$ 依次拼接，得到新的字符串 $t$。

你可以对字符串 $s$ 进行操作，每次操作可以交换任意两个字符的位置，注意操作不是实际改变，不会影响后续的询问。定义对于字符串 $s$，$f(s)$ 表示最小的操作次数，使得拼接得到的新字符串 $t$ 的字典序最大。

然后有 $q$ 次询问，每次询问给出一个位置 $x_i$，表示将原字符串 $s$ 的 $x_i$ 位置取反，注意是实际改变，会影响后续的询问。相应的，$t$ 字符串也会发生改变。你需要求出每次询问后，$f(s)$ 的值。

By Binary_1110011_

solution

需要对字符串的下标按权值排序。

对于下标i，如果在按顺序给出m个区间中，首先出现在第j个区间$[l_j, r_j]$，那么给i的权值为$w_i=j$，对于没有出现在任何区间的i，$w_i=m+1$

我们将下标按照权值升序排序，并对于权值相等的下标较小的排前面。排序后我们可以将原始下标$i$映射到新的下标$rid_i$。

构造出排序后的字符串$rs$，所求的$t$需要字典序最大化。设m个区间总共覆盖了$cov$个不重复的下标，实际上就是让$rs$前$cov$个字符字典序最大化。

后续的询问q次，每个修改的下标$x$将成为$rid_x$，反转$rs_{ris_x}$。

现在问题转化为了$rs$中每次反转一个字符，然后可以通过交换任意两个字符的操作达到字典序最大化，并且求最少操作次数。

设$c1$为当前字符串中1的个数。我们只需要让至多$cov$个1（即$min(c1,cov)$个1）放到字符串的开头即可。前$min(c1,cov)$个字符中的0的个数就是要交换的次数。

为求出$w$，可以用懒标记线段树，只需支持区间覆盖单点查询。但这并不是最好的实现方式，可以用set逐个删除对应区间的元素。

需要多次求前缀和，用树状数组。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 200005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

struct Seg{
	int l, r;
	ll val, tag;
} seg[N<<2];


// 将当前区间的懒标记，作用到左右区间（改变区间值），并将标记传递给子区间（累加，子区间可能存在未传递的懒标记），删除当前区间的懒标记。
void push_down(Seg& u, Seg& l, Seg& r) {
    if (u.tag == 0) return ;
	l.val = u.tag;
	l.tag = u.tag;
	r.val = u.tag;
	r.tag = u.tag;
	u.tag = 0;
}

void seg_build(int id, int l, int r, int val) {
	seg[id].l = l; seg[id].r = r;
	if (l == r) {
        seg[id].val = val;
		return ;
	}
	int m = l+r>>1;
	seg_build(id<<1, l, m, val);
	seg_build(id<<1|1, m+1, r, val);
}

void seg_update(int id, int l, int r, ll val) {
	if (l <= seg[id].l && seg[id].r <= r) {
		seg[id].val = val;
		seg[id].tag = val;
		return ;
	}
	push_down(seg[id], seg[id<<1], seg[id<<1|1]);
	int m = seg[id].l + seg[id].r >> 1;
	if (l <= m) seg_update(id<<1, l, r, val);
	if (m < r) seg_update(id<<1|1, l, r, val);
}

ll seg_query(int id, int p) {
	if (seg[id].l == seg[id].r) {
		return seg[id].val;
	}
	push_down(seg[id], seg[id<<1], seg[id<<1|1]);
	int m = seg[id].l + seg[id].r >> 1;
	if (p <= m) return seg_query(id<<1, p);
	else return seg_query(id<<1|1, p);
}

ll BIT[N];
// ll xBIT[N];

void bit_add(int x, ll val) {
    for (int i=x; i<N; i+=i&-i) {
        BIT[i] += val;       
        // xBIT[i] += x*val;
        // 区间查询时 BIT[i] += val; xBIT[i] += x*val;
    }
}

ll bit_ps(int x) {
    ll rt = 0;
    for (int i=x; i>0; i-=i&-i) {
        rt += BIT[i];
        // rt += x*BIT[i]-xBIT[i];
        // 区间查询时 rt += (x+1)*BIT[i]-xBIT[i];
    }
    return rt;
}

void sol() {
    int n, m, q;
    cin >> n >> m >> q;
    string s;
    cin >> s;
    s = "#" + s;
    vector<pair<int,int>> sg(m);
    for (auto& [i,j]:sg) cin >> i >> j;
    reverse(sg.begin(), sg.end());
    seg_build(1, 1, n, m+1);
    for (int i=0; i<m; i++) {
        auto [l, r] = sg[i];
        seg_update(1, l, r, m-i);
    }
    vector<int> v(n+1);
    for (int i=1; i<=n; i++) {
        v[i] = seg_query(1, i);
    }
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 1);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        int vx = v[x], vy = v[y];
        if (vx == vy) return x < y;
        return vx < vy;
    });
    int cov = 0;
    for (int i=1; i<=n; i++) {
        if (v[i] != m+1) cov++;
    }
    string rs = "@";
    vector<int> rid(n+1);
    for (int i=0; i<n; i++) {
        rid[idx[i]] = i+1;
        rs.push_back(s[idx[i]]);
        if (s[idx[i]] == '1') bit_add(i+1, 1);
    }
    int c1 = count(s.begin(), s.end(), '1');
    while (q--) {
        int x;
        cin >> x;
        x = rid[x];
        int v;
        if (rs[x] == '1') rs[x] = '0', v = -1;
        else rs[x] = '1', v = 1;
        bit_add(x, v);
        c1 += v;
        int cnt = min(c1, cov);
        cout << cnt-bit_ps(cnt) << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}