P6859 蝴蝶与花 思维 + 数据结构优化

P6859 蝴蝶与花 思维 + 数据结构优化

题意

给定一个(12)串，问能否找到(l)最小的区间([l,r])使得(sum[l,r])恰好等于(s)

过程中可以修改单点，修改后也只能是(1或者2)

串的长度(n)，(m)次询问

对每个询问若有合法方案输出这个方案的(l,r)否则输出(none)

[1leq n ,mleq 2 imes 10^6\ 0leq s le 2^{31}-1 ]

分析

显然不能直接暴力

我们利用前缀和维护区间和，如果以1为起点，二分出和不小于(k)的(r)，容易发现而分出的区间的和要么是(k)，要么是(k+1)。

假设二分出([l,r_1]),([l+1,r_2])且两个区间的和都是(k+1)

可以发现

• (a_l = 2)
• (a_{r1} = 2)
• (r2 = r1 + 1)

这样发现其实和连续(2)的个数有关。

规律总结后有如下性质：

二分出从位置1的开始和不小于(k)的右端点(p)。利用数据结构求出位置1和位置(p)后连续(2)的个数分别为(cnt1,cnt2)

• (cnt1 < cnt2) 时，区间([2 + cn1,p + cnt1])就是答案
• (cnt1 geq cnt2)时，区间([1 + cnt2,p+cnt2])就是答案

只需要解决两个问题

• 如何找到第一个前缀和不小于(k)的位置
• 如何求出一个位置后面有多少个连续的2

这两个问题都可以在树状数组内2分实现（注意如果用2分 + 树状数组 复杂度会多一个log）

对于问题2，只需要判断区间([p,p + len - 1])的和是否是(2 imes len)即可

当然也可以用线段树复杂度(O(mlogn))

代码

ll c[maxn];

struct BIT {
    int n;
    void add(int x, int y) {
        for (int i = x; i < maxn; i += i & -i) {
            c[i] += y;
        }
    }
    int query(int x) {
        ll res = 0;
        for (int i = x;i; i -= i & -i) {
            res += c[i];
        }
        return res;
    }
    int query1(int k) {
        int p = 0, sum = 0;
        for (int i = 20; i >= 0; i--) {
            int s = (1 << i);
            if (sum + c[s + p] <= k) p += s, sum += c[p];
        }
        return p;
    }
    int query2(int k) {
        int p = 0, sum = 0;
        int tmp = query(k - 1);
        for (int i = 20; i >= 0; i--) {
            int s = (1 << i);
            if ((sum + c[p + s] - tmp == (p + s - k + 1) * 2) || (p + s < k))
                p += s, sum += c[p];
        }
        return p;
    }
};

int a[maxn];


int main() {
    int n = readint();
    int m = readint();
    BIT bit;
    bit.n = n;
    for (int i = 1; i <= n; i++)
        a[i] = readint(), bit.add(i, a[i]);
    bit.add(n + 1, 1e9);
    char op[5];
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'C') {
            int x = readint();
            int y = readint();
            bit.add(x, y - a[x]);
            a[x] = y;
        }
        else {
            int x = readint();
            int pos = bit.query1(x);
            if (!x || x > bit.query(n)) puts("none");
            else if (bit.query(pos) == x) printf("%d %d
", 1, pos);
            else {
                pos++;
                int len1 = bit.query2(1), len2 = bit.query2(pos) - pos + 1;
                if (len1 < len2) {
                    if (pos + len1 <= n) printf("%d %d
", 2 + len1, pos + len1);
                    else puts("none");
                }
                else {
                    if (pos + len2 <= n) printf("%d %d
", 1 + len2, pos + len2);
                    else puts("none");
                }
            }
        }
    }
}