洛谷P5072 [YNOI2015]盼君勿忘莫队+unordered

本文主要是介绍洛谷P5072 [YNOI2015]盼君勿忘莫队+unordered_set+毒瘤卡常，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人，人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

珂朵莉最可爱了，~~珂朵莉的题最毒瘤了qwq~~

题目链接：传送门

这是一个自带大常数选手被毒瘤 $l x l$ 卡常数，从开 $O 2$ 才 $82$ 分到不开 $O 2$ 就珂 $A C$ 的故事……

先上图QWQ

在这里插入图片描述

解题思路

一开始没看懂题……“子序列”是不需要连续的……
序列上一段区间内的问题，不带修改， $n\leq 100000$ ，~~又是YNOI的题~~，容易想到莫队。
发现每次大力去重显然复杂度爆炸，又因为 $a_i<=10^5$ ，因此考虑每个数对答案的贡献。
考虑区间 $[l, r]$ 。显然这个区间的子序列总数为 $2^{r-l+1}$ 。
假设一个数 $x$ 在区间 $[l, r]$ 中出现了 $k$ 次，那么不含 $x$ 的子序列总个数为 $2^{r-l+1-k}$ 。
所以 $x$ 对答案的贡献为 $x*(2^{r-l+1}-2^{r-l+1-k})$
发现大莉统计答案也会爆，所以开一个set（这里为了减小复杂度，用了unordered_set）来保存所有出现过的出现过的次数。
也就是说，比如若 $[l, r]$ 中有一个数出现了 $1$ 次，有一个数出现了 $3$ 次，那么 $s e t$ 里就保存了 $1, 3 .$
然后每次就珂以大莉莫队，修改在set上乱改一波，询问大莉统计就珂以了qwq
时间复杂度 $O(m\sqrt{n}logn)$ （莫队 $O(m\sqrt{n})$ ，快速幂 $O (l o g n)$ ）
……
…………
………………
TLE？？？
掐指一算， $m*\sqrt{n}*logn$ 差不多为 $10^5*300*16=4.8*10^8$ ……
珂能其他题卡一卡就过去了，但是毒瘤的YNOI题肯定是不会放过这种错误时间复杂度过的qwq
于是考虑优化。

优化过程

首先把 $\sqrt n$ 优化掉不太现实（~~不然lxl就不会把n,m只开到1e5~~），因为莫队必然会带 $\sqrt n$ 的复杂度qwq。
所以考虑把快速幂的 $\log n$ 的复杂度去掉（以下想法参考这个题解）：
发现如果把 $2^1,2^2,2^3,...,2^{\sqrt n-1}$ 和 $2^{\sqrt n},2^{2\sqrt n},...,2^n$ 预处理出来，
就珂以把一个 $2^x$ 表示成 $2^{k\sqrt n}*2^q$ ，然后 $O (1)$ 求。这里 $k=x/\sqrt{n},q=x$ $m o d$ $\sqrt n$ 。
于是大莉写一波啊qwq
时间复杂度 $O(m\sqrt{n})$
……
…………
………………
TLE？？？？？
笑容逐渐消失.jpg
发现总是有几个点过不去……时间复杂度应该已经最优了……于是又要卡一波常数……

卡常技巧

$1 .$ 快读快写、 $r e g i s t e r$ 和 $i n l i n e$ （对于像我这样的大常数选手来说，这是必备的qwq）

$2 .$ 莫队的奇偶性玄学优化（参考这篇博客qwq）

$3 .$ 减少取模次数：
假设 $p w 1 [i]$ 表示 $2^i$ ，那么原本写的是：

pw1[i]=(pw1[i-1]<<1)%mod;

要改成：

pw1[i]=(pw1[i-1]<<1)<mod?pw1[i-1]<<1:(pw1[i-1]<<1)-mod;

实测这样珂以很有效地减小常数

$4 .$ 减小除法与取模次数：
发现算 $2$ 的幂时还是要重复算很多次除法和取模，这里珂以把 $\frac{i}{\sqrt n}$ 和 $i$ $m o d$ $\sqrt n$ 都预处理出来，然后直接调用qwq。
这样也珂以大减一波常数qwq

$5 .$ 把 $+ + r$ 和 $l - -$ 之类的东西和附近的操作合并一下，比如 $a [+ + r]$ 和 $a [l - -]$

提交……
终于过了QWQ
~~索然无味……~~

毒瘤代码

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<unordered_set>
#define re register int
using namespace std;
typedef long long ll;
typedef unordered_set<int>::iterator svi;
inline char getc() {    //优化的getchar static char buf[262145],*fs,*ft;return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}
int read() {re x=0,f=1;char ch=getc();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getc();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getc();}return x*f;
}
inline void write(int x) {if(x>9)	write(x/10);putchar(x%10+'0');
}
const int Size=100005;
int n,m,siz,a[Size],belong[Size];
struct Query {int id,l,r,p;
} Q[Size];
inline bool comp(Query x,Query y) {if(belong[x.l]!=belong[y.l])	return x.l<y.l;if(belong[x.l]&1)	return x.r<y.r;return x.r>y.r;
}
ll pw1[Size],pw2[Size];
int MOD[Size],DIV[Size];
inline ll fastpow(int n,int mod) {//算 2^n %mod 的值 return pw1[MOD[n]]*pw2[DIV[n]]%mod;
}
int vis[Size],val[Size],ans[Size];
unordered_set<int> Union;
void add(int x) {if(vis[x]) {val[vis[x]]-=x;if(!val[vis[x]]) {Union.erase(vis[x]);}}if(!val[++vis[x]])	Union.insert(vis[x]);val[vis[x]]+=x;
}
void del(int x) {val[vis[x]]-=x;if(!val[vis[x]])	Union.erase(vis[x]);if(--vis[x]) {if(!val[vis[x]]) {Union.insert(vis[x]);}val[vis[x]]+=x;}
}
int main() {n=read();m=read();//发现siz好像取m/sqrt(n)时常数小一点 //这里取sqrt(n)好像也是珂以的qwq siz=m/sqrt(n);for(re i=1; i<=n; i++) {//预处理出i/siz和i%siz的值 MOD[i]=i%siz;DIV[i]=i/siz;}for(re i=1; i<=n; i++) {a[i]=read();belong[i]=i/siz+1;}for(re i=1; i<=m; i++) {Q[i].l=read();Q[i].r=read();Q[i].p=read();Q[i].id=i;}sort(Q+1,Q+1+m,comp);pw1[0]=pw2[0]=1;int l=1,r=0;for(int i=1; i<=m; i++) {while(r<Q[i].r)	add(a[++r]);while(r>Q[i].r)	del(a[r--]);while(l<Q[i].l)	del(a[l++]);while(l>Q[i].l)	add(a[--l]);int mod=Q[i].p;//每次暴力O(sqrt(n))预处理2的幂 for(re i=1; i<=siz; i++) {
//			pw1[i]=(pw1[i-1]<<1)%mod;pw1[i]=(pw1[i-1]<<1)<mod?pw1[i-1]<<1:(pw1[i-1]<<1)-mod;}pw2[1]=pw1[siz];for(re i=2; i<=siz; i++) {pw2[i]=pw2[i-1]*pw2[1]%mod;}int len=Q[i].r-Q[i].l+1;re sum=0;for(svi it=Union.begin(); it!=Union.end(); it++) {//恶臭无比 sum=(sum+val[*it]*(fastpow(len,mod)-fastpow(len-(*it),mod)+mod))%mod;}ans[Q[i].id]=sum;}for(re i=1; i<=m; i++) {write(ans[i]);putchar(10);}return 0;
}