洛谷 4887 第十四分块「前体」

发表于 | 分类于 | 29

有趣的科技。Orz lxl。

首先考虑一个裸的莫队解法，用一个桶存一下，每次暴力找新增的贡献即可。
复杂度是 O(n√n(14k))。
显然过不掉啊……

注意到这个 O((14k)) 来自于新增的贡献，于是可以考虑优化这一过程。
考虑从 [l,r] 转移到 [l,r+k]，设 c(x,[l,r]) 表示 x 对 [l,r] 的贡献，则总贡献为 r+k∑i=r+1c(i,[l,i))=r+k∑i=r+1[c(i,[1,i))−c(i,[1,l))]

于是贡献就被分成了两种：c(i,[1,i)) 和 c(i,[1,r])。
前一种一定只会有 n 个，于是一遍 O(n(14k)) 处理。
后一种，注意到每次转移时，计算贡献的区间都是同一个，而移动的位置只会有 O(n√n) 个，于是可以轻易做到总复杂度 O(n(14k)+n√n)。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int C = 16384;
int n,m,k,a[N + 5];
int cnt[C + 5],sum[N + 5];
int block,pos[N + 5];
long long ans[N + 5];
struct s_query
{
    int l,r,id;
    long long ans;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] ^ pos[o.l] ? l < o.l : ((pos[l] & 1) ? r < o.r : r > o.r);
    }
} qry[N + 5];
struct s_contrib
{
    int l,r,id,w;
};
vector<int> w;
vector<s_contrib> vec[N + 5];
int main()
{
    scanf("%d%d%d",&n,&m,&k),block = sqrt(n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
    if(k > 14)
    {
        for(register int i = 1;i <= m;++i)
            puts("0");
        return 0;
    }
    sort(qry + 1,qry + m + 1);
    for(register int i = 0;i < C;++i)
        __builtin_popcount(i) == k && (w.push_back(i),1);
    for(register int i = 1;i <= n;++i)
    {
        sum[i] = cnt[a[i]];
        for(vector<int>::iterator it = w.begin();it != w.end();++it)
            ++cnt[a[i] ^ *it];
    }
    for(register int i = 1,l = 1,r = 0;i <= m;++i)
    {
        l < qry[i].l && (vec[r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
        for(;l < qry[i].l;qry[i].ans += sum[l],++l);
        l > qry[i].l && (vec[r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
        for(;l > qry[i].l;qry[i].ans -= sum[l - 1],--l);
        r < qry[i].r && (vec[l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
        for(;r < qry[i].r;qry[i].ans += sum[r + 1],++r);
        r > qry[i].r && (vec[l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
        for(;r > qry[i].r;qry[i].ans -= sum[r],--r);
    }
    memset(cnt,0,sizeof cnt);
    for(register int i = 1;i <= n;++i)
    {
        for(vector<int>::iterator it = w.begin();it != w.end();++it)
            ++cnt[a[i] ^ *it];
        for(vector<s_contrib>::iterator it = vec[i].begin();it != vec[i].end();++it)
            for(register int j = it->l;j <= it->r;++j)
                qry[it->id].ans += it->w * (cnt[a[j]] - (j <= i && !k));
    }
    for(register int i = 1;i <= m;++i)
        ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans);
    for(register int i = 1;i <= m;++i)
        printf("%lld\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment