题解 [email protected]洛谷 【[Ynoi2015]盼君勿忘】

给定一个序列,每次查询一个区间 [l,r][l,r] 中所有子序列分别去重后的和  smodps\bmod{p} 的结果。


乍一看好像不太可做,仔细分析发现有点规律:

在一个长度为 aa 的序列中,一个数出现次数为 bb。则有 2ab2^{a-b} 个子序列不包含该元素,它的贡献是 2a2ab2^a-2^{a-b}

问题转化为如何快速求出每一个数的贡献值。

10510^5、离线、维护数列,想到什么?莫队!

我们使用莫队记录双向链表(建议手写),维护每个数分别的出现次数,下标表示数,内容为出现次数。则这个链表的元素个数大致在 n\sqrt{n} 级别。在跳到当前区间后,枚举维护的链表,对于每个元素分别算出贡献值后相加即可。

还剩下最后一个问题:如何快速求出 2k2^k?普通的快速幂可能做不到,因为带一只 log\log,容易被卡。果断选用光速幂

光速幂是什么呢?就是一种 O(n)\mathcal{O(\sqrt{n})} 预处理、O(1)\mathcal{O(1)} 查询的,求特定底数的幂的快速方法。具体方案是:预处理 21,22,,2n2^1,2^2,\cdots,2^{\sqrt{n}}2n,22×n,,2n2^{\sqrt{n}},2^{2\times\sqrt{n}},\cdots,2^n,然后根据商和余数即可 O(1)\mathcal{O(1)} 求出结果。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5;

ll n, m, a[N], SIZE, cnt[N], s[N], ans[N];
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
struct Query {
	ll l, r, p, id;
	Query(ll a=0, ll b=0, ll c=0, ll d=0) : l(a), r(b), p(c), id(d) {}
	~Query() {}
	friend bool operator < (const Query &a, const Query &b) {
		ll x = whichBlock(a.l), y = whichBlock(b.l);
		if(x == y) return a.r < b.r;
		return x < y;
	}
}q[N];
struct myList {
	struct Node {
		ll pre, nxt;
		Node(ll a=0, ll b=0) : pre(a), nxt(b) {}
		~Node() {}
	}nd[N];
	ll tot;
	myList(ll a=0) : tot(a) {}
	~myList() {}
	void insert(ll x) {
		nd[tot].nxt = x;
		nd[x].pre = tot;
		tot = x;
	}
	void erase(ll x) {
		if(x != tot) {
			nd[nd[x].pre].nxt = nd[x].nxt;
			nd[nd[x].nxt].pre = nd[x].pre;
		}
		else {
			nd[nd[x].pre].nxt = 0;
			tot = nd[x].pre;
		}
		nd[x] = Node();
	}
}lst;
namespace qpow {
	ll pow1[N], pow2[N];
	void initPow(ll mod) {
		pow1[0] = pow2[0] = 1;
		for(ll i=1;i<=SIZE;i++) pow1[i] = pow1[i-1] * 2 % mod;
		for(ll i=1;i<=SIZE;i++) pow2[i] = pow2[i-1] * pow1[SIZE] % mod;
	}
	ll calc(ll x, ll mod) {return pow1[x%SIZE]*pow2[x/SIZE]%mod;}
}
void upd(ll x, ll k) {
	if(!(s[cnt[a[x]]]-=a[x])) lst.erase(cnt[a[x]]);
	if(!s[cnt[a[x]]+=k]) lst.insert(cnt[a[x]]);
	s[cnt[a[x]]] += a[x];
}

int main() {
	scanf("%lld%lld", &n, &m);
	SIZE = sqrt(n);
	for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
	for(ll i=1;i<=m;i++) scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].p), q[i].id = i;
	sort(q+1, q+1+m);
	ll l = 1, r = 0;
	for(ll i=1;i<=m;i++) {
//		printf("QUERY #%d: id=%d l=%d r=%d p=%d\n", i, q[i].id, q[i].l, q[i].r, q[i].p);
		qpow::initPow(q[i].p);
		while(l > q[i].l) upd(--l, 1);
		while(r < q[i].r) upd(++r, 1);
		while(l < q[i].l) upd(l++, -1);
		while(r > q[i].r) upd(r--, -1);
		for(ll j=lst.nd[0].nxt;j;j=lst.nd[j].nxt) {
//			printf("LIST POSITION: %d\n", j);
			ll _1 = qpow::calc(r-l+1, q[i].p);
			ll _2 = qpow::calc(r-l+1-j, q[i].p);
			ll _3 = ((_1 - _2) * s[j] + q[i].p) % q[i].p;
			ans[q[i].id] = (ans[q[i].id] + _3 + q[i].p) % q[i].p;
		}
	}
	for(ll i=1;i<=m;i++) printf("%lld\n", ans[i]);
	return 0;
}