2020牛客多校第五场H

题目链接

有一个长为$n$的序列$A$，设$F(l,r)=A_l\&A_{l+1}\&A_{l+2}…\&A_r$，给定$S(l,r)=\{F(a,b)|min(l,r)\le a \le b \le max(l,r)\}$

现在进行$Q$次查询，对于每个查询，请你求出给定$(L,R)$的$S(l,r)$的大小，$L,R$将不会直接给出，它会给你$L’$和$R’$

$L = (L’ \oplus lastans)\%N + 1$

$R=(R’ \oplus lastans)\%N +1$

分析：

每次读入一个数$x$，暴力地将所有之前的结果和$x$相与，存入数组。并更新它们的位置为最靠近$i$的位置。

$pre[]$记录每个相与的结果的前一个位置

主席树$root[i]$代表第$i$个版本的线段树，下标为位置，每个位置存的是该位置有多少个不同的相与的结果，然后查询$[l,r]$不同的结果个数时，直接在第$r$个版本的线段树中查询$[l,r]$即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 100005;

struct Node
{
    int l, r;
    int sum;
}tr[N * 400];//不知道这里为什么400就过了

int n, m;
int a[N], root[N], idx;
unordered_map<int, int> num_pos, tmp, lst;

void pushup(int u)
{
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

int insert(int p, int l, int r, int x, int c)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if(l == r)
    {
        tr[q].sum += c;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x, c);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x, c);
    pushup(q);
    return q;
}

int query(int p, int l, int r, int ql, int qr)
{
    if(!p) return 0;
    if(ql <= l && qr >= r) return tr[p].sum;
    int mid = l + r >> 1;
    int res = 0;
    if(l <= mid) res += query(tr[p].l, l, mid, ql, qr);
    if(r > mid) res += query(tr[p].r, mid + 1, r, ql, qr);
    return res;
}

int main()
{
    scanf("%d", &n);
    root[0] = ++ idx;
    for(int i = 1; i <= n; i ++ )
    {
        tmp.clear();
        int x;
        scanf("%d", &x);
        root[i] = root[i - 1];
        //当前数字最后出现的位置
        num_pos[x] = i;
        //当前数字和之前的所有数相与，并更新它们为最靠近i的位置
        for(auto &[a, pos]:num_pos) tmp[a & x] = max(tmp[a & x], pos);
        //在主席树上更新与值为最靠近i的位置
        for(auto &[a, b]:tmp)
        {
            if(lst[a] != b)
            {
                if(lst[a]) root[i] = insert(root[i], 1, n, lst[a], -1);
                lst[a] = b;
                root[i] = insert(root[i], 1, n, b, 1);
            }
        }
        num_pos = tmp;
    }
    scanf("%d", &m);
    int ans = 0;
    while(m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l ^ ans) % n + 1;
        r = (r ^ ans) % n + 1;
        if(l > r) swap(l, r);
        ans = query(root[r], 1, n, l, r);
        printf("%d\n", ans);
    }

    return 0;
}

HDU-5869 Different GCD Subarray Query

$ 1≤N,Q≤100000$

$ 1≤a_i≤1000000$

首先需要先说明下gcd的性质

假设我们固定右端点（注意后面我们都是固定右端点），区间向左延伸，那么gcd个数一定是呈现非递增性质的，即要么不变要么减小，并且减小的话一定减少一半，因为实际上一段区间内，不同的gcd的个数，不会超过log个

那么假设我们已经求出了区间[1,r]的不同gcd了，那么求[1,r+1]的时候，我们只需要用r+1的这个数即a[r+1]，和前一区间内已经求出的gcd进行求gcd就行了，不需要在一个一个枚举每个数求gcd了，也就是相当于要求[k，r+1]的gcd的时候[k,r]的gcd已经在上次求好了，我们直接再与a[r+1]这个数求一次gcd就好了，这样就大大减小了复杂度

由于刚才说的gcd的非递增性质，如果存在一个gcd = g，那么要想得到这g，一定存在一个最大的左端点lmlm，即我们从r+1向左遍历的时候，到lmlm的时候第一次得到gcd=g，继续向左走的话要么还是g，要么一定变得比g小，因此再往左走就再也不会得到g了，这就是所说的每个gcd都有一个最大的左端点。

所以我们可以利用这最大左端点作为位置，往树状数组里面存，进行不断更新

为了提高效率需要使用离线查询，先把查询存下来，按照右端点从小到大排序

我们仍然是先移动R，在移动过程中不断更新树状数组，这样当R满足第一个查询区间的r，用树状数组查询区间[l,r]即可，因为当我们更新完成后，查询区间[l,r]实际上个相当于查询gcd最大左端点是>=l的个数，小于l的说明得再往左移动才能得到一个新的不同gcd，而右端点我们只更新到了R，也即是要求区间右端点r因此保证了正确性

树状数组版本的：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1000005;

int n, m;
int tr[N], a[N], pre[N], ans[N];

struct Query
{
    int id;
    int l, r;
    bool operator< (const Query &t) const
    {
        return r < t.r;
    }
}q[N];

vector<PII> G[N];// 每个pair存的是{gcd,最大下标}

int lowbit(int x)  // 返回末尾的1
{
    return x & -x;
}


int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void solve()
{
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++ ) G[i].clear();
    for(int i = 1; i <= n; i ++ )
    {
        int x = a[i], y = i;
        for(int j = 0; j < G[i - 1].size(); j ++ )
        {
            auto tmp = G[i - 1][j];
            int res = gcd(x, tmp.first);
            if(x != res)
            {
                G[i].push_back({x, y});
                x = res;
                y = tmp.second;
            }
        }
        G[i].push_back({x, y});
    }
    memset(tr, 0, sizeof tr);
    memset(pre, 0, sizeof pre);
    for(int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m);
    for(int R = 0, i = 0; i < m; i ++ )
    {
        while(R < q[i].r)
        {
            R ++;
            for(int j = 0; j < G[R].size(); j ++ )
            {
                int res = G[R][j].first;
                int pos = G[R][j].second;
                if(pre[res]) add(pre[res], -1);
                pre[res] = pos;
                add(pre[res], 1);
            }
        }
        ans[q[i].id] = sum(R) - sum(q[i].l - 1);
    }
    for(int i = 0; i < m; i ++ ) printf("%d\n", ans[i]);
}

int main()
{
    while(~scanf("%d%d", &n, &m)) solve();
    return 0;
}

主席树版本的（会爆空间）：

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct Node
{
    int l, r;
    int sum;
}tr[N * 30];

int n, m;
int a[N], root[N], idx;
unordered_map<int, int> num_pos, tmp, lst;

int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

void pushup(int u)
{
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

int insert(int p, int l, int r, int x, int c)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if(l == r)
    {
        tr[q].sum += c;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x, c);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x, c);
    pushup(q);
    return q;
}

int query(int p, int l, int r, int ql, int qr)
{
    if(!p) return 0;
    if(ql <= l && qr >= r) return tr[p].sum;
    int mid = l + r >> 1;
    int res = 0;
    if(ql <= mid) res += query(tr[p].l, l, mid, ql, qr);
    if(qr > mid) res += query(tr[p].r, mid + 1, r, ql, qr);
    return res;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        num_pos.clear();
        lst.clear();
        idx = 0;
        root[0] = 0;
        for(int i = 1; i <= n; i ++ )
        {
            tmp.clear();
            int x;
            scanf("%d", &x);
            root[i] = root[i - 1];
            num_pos[x] = i;
            for(auto it : num_pos)
            {
                int a = it.first, pos = it.second;
                int ttt = gcd(a, x);
                tmp[ttt] = max(tmp[ttt], pos);
            }
            for(auto it : tmp)
            {
                int a = it.first, b = it.second;
                if(lst[a] != b)
                {
                    if(lst[a]) root[i] = insert(root[i], 1, n, lst[a], -1);
                    lst[a] = b;
                    root[i] = insert(root[i], 1, n, b, 1);
                }
            }
            num_pos = tmp;
        }
        while(m -- )
        {
            int l, r;
            scanf("%d%d", &l, &r);
            cout << query(root[r], 1, n, l, r) << endl;
        }
    }


    return 0;
}

牛客练习赛91–C 并查集区间染色

原题链接

首先将所有的染色方案倒过来，这样每个点只会被染色一次

设$vis[i]$表示第$i$个点的颜色

for(int i = m - 1; i >= 0; i -- )
{
    for(int j = q[i].r; j >= q[i].l;)
    {
        int t = find(j);
        if(t == j) 
        {
            vis[j] = q[i].c, fa[j] = find(j - 1);
        }
        j = fa[j];
    }
}