http://codeforces.com/contest/400

E题
首先注意到每个位是互不影响的,所以问题可以转化为单个 01 序列的 AND 操作。
怎么统计呢?画个右对齐的数字三角形就知道了,找当前修改的位置左右最近的0就行。

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = 1e5 + 5;
int a[mx];
set<int> pos[18];
set<int>::iterator low, up;
ll sum[18];

inline void one(int p, int v)
{
    pos[p].erase(v);
    low = up = pos[p].upper_bound(v);
    sum[p] += ll(v - *--low) * (*up - v);
}

inline void zero(int p, int v)
{
    low = up = pos[p].upper_bound(v);
    sum[p] -= ll(v - *--low) * (*up - v);
    pos[p].insert(v);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < 18; i++) for (int j = 0; j <= n + 1; j++) pos[i].insert(j);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < 18; i++) for (int j = 0; j <= n + 1; j++) if (a[j] >> i & 1) one(i, j);
    while (m--)
    {
        int p, v;
        scanf("%d%d", &p, &v);
        for (int i = 0; i < 18; i++)
        {
            if (v >> i & 1) {if (pos[i].count(p)) one(i, p);} // 修改前是0
            else if (!pos[i].count(p)) zero(i, p); // 修改前是1
        }
        ll ans = 0;
        for (int i = 0; i < 18; i++) ans += sum[i] * (1 << i);
        printf("%I64d\n", ans);
    }
    return 0;
}

Comments

comments powered by Disqus