洛谷 5072 「Ynoi 2015」盼君勿忘

发表于 | 分类于 |

既然去重，则可以考虑每一种数的贡献。
实际上就是这一种数在 \([l,r]\) 的子序列中出现的次数。

对于某种数，设其在区间内出现次数为 \(k\)，则不包含这种树的子序列有 \(2^{r-l+1-k}\) 个。
而这个区间总共的子序列有 \(2^{r-l+1}\) 个。

这样显然不能过。
考虑把贡献次数相同，即出现的子序列个数相同，也即出现次数相同的数放在一起做。
然后莫队。

那么又注意到实际上不同的出现次数只会有 \(O(\sqrt n)\) 种。
因为要最大化不同的出现次数的种数，则显然要从小的出现次数开始选。
这个区间的长度本身是 \(O(n)\) 的，那么根据等差数列求和公式可得最多有 \(O(\sqrt n)\) 种。
然后就 OJBK 辣。

注意每个询问的模数是不同的，那是不是得带个 log 算快速幂呢？
并不，可以预处理模意义下的 \(1,2,2^2,2^3,\ldots,2^T\) 和 \(1,2^T,2^{2T},...,2^{\lfloor\frac nT\rfloor T}\)，其中 \(T\) 为块大小。

如果用 set/unordered_set 来存储不同的出现次数的话常数会很大，需要高超的卡常技巧彩星。
然鹅实际上可以直接用一个 vector 来存，转移询问的时候保留上一次的值，并且不删除无用值，而是转移完之后重构 vector，此时再将无用值删去。
复杂度可以根据莫队的移动次数和上述不同出现次数的结论得到。

代码： 

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 1e5;
const int BLK = 318;
const int CNT = 320;
int n,m,a[N + 5];
int block,pos[N + 5];
struct s_query
{
    int l,r,mod,id;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
    }
} qry[N + 5];
int pw1[N + 5],pw2[N + 5];
int cnt[N + 5],vis[N + 5];
long long sum[N + 5];
vector<int> d,temp;
int ans[N + 5];
inline void add(int x)
{
    if(cnt[a[x]])
        sum[cnt[a[x]]] -= a[x];
    if(!sum[++cnt[a[x]]] && !vis[cnt[a[x]]])
        vis[cnt[a[x]]] = 1,d.push_back(cnt[a[x]]);
    sum[cnt[a[x]]] += a[x];
}
inline void del(int x)
{
    sum[cnt[a[x]]] -= a[x];
    if(--cnt[a[x]])
    {
        if(!sum[cnt[a[x]]] && !vis[cnt[a[x]]])
            vis[cnt[a[x]]] = 1,d.push_back(cnt[a[x]]);
        sum[cnt[a[x]]] += a[x];
    }
}
inline long long pow2(int x)
{
    return (long long)pw1[x % block] * pw2[x / block];
}
int main()
{
    read(n),read(m),block = BLK,pw1[0] = pw2[0] = 1;
    for(register int i = 1;i <= n;++i)	
        read(a[i]),pos[i] = (i - 1) / block + 1;
    for(register int i = 1;i <= m;++i)
        read(qry[i].l),read(qry[i].r),read(qry[i].mod),qry[i].id = i;
    sort(qry + 1,qry + m + 1);
    for(register int i = 1,l = 1,r = 0;i <= m;++i)
    {
        for(;r < qry[i].r;add(++r));
        for(;l > qry[i].l;add(--l));
        for(;r > qry[i].r;del(r--));
        for(;l < qry[i].l;del(l++));
        for(register int j = 1;j <= block;++j)
            pw1[j] = 2LL * pw1[j - 1] % qry[i].mod;
        for(register int j = 1;j * block <= n;++j)
            pw2[j] = (long long)pw2[j - 1] * pw1[block] % qry[i].mod;
        temp.clear();
        for(register vector<int>::iterator it = d.begin();it != d.end();++it)
            sum[*it] ? (temp.push_back(*it),1) : (vis[*it] = 0);
        d = temp;
        for(register vector<int>::iterator it = d.begin();it != d.end();++it)
            ans[qry[i].id] = (ans[qry[i].id] + (pow2(qry[i].r - qry[i].l + 1) - pow2(qry[i].r - qry[i].l + 1 - *it)) % qry[i].mod * sum[*it]) % qry[i].mod;
        ans[qry[i].id] = (ans[qry[i].id] + qry[i].mod) % qry[i].mod;
    }
    for(register int i = 1;i <= m;++i)
        printf("%d\n",ans[i]);
}