@[mashduihca](/user/494183) 谢教%%%\
@waauto A队%%%\
@[syta](/user/505643) syt大佬%%%\
@[operator_](/user/499682) 大佬%%%\
@sjjbszgyd zhb%%%\
@zhaohanwen ds大佬%%%\
@[OcTar](/user/594916) 折磨牛%%%
by ReturnOrContinue @ 2024-02-21 19:44:44
@[zhaohanwen](/user/767660) ?\
@sjjbszgyd ?
by ReturnOrContinue @ 2024-02-21 19:46:57
@[ReturnOrContinue](/user/767588) 能不能把代码粘全/kel，编译不过去/fad
by h_rains @ 2024-02-22 14:01:50
@[waauto](/user/355192)
by sjbbszgyd @ 2024-02-22 14:49:20
@[h_rains](/user/665801) 在机房，拿不到源代码（
by ReturnOrContinue @ 2024-02-22 14:52:52
@[ReturnOrContinue](/user/767588) ？你不是交在洛谷上了嘛/yiw
by h_rains @ 2024-02-22 15:00:18
@[h_rains](/user/665801) 我想起来了
```cpp
#include <bits/stdc++.h>
#define Arknights return
#define AK 0
#define IOI ;
#define ll long long
#define ld long double
#define ull unsigned ll
#define lll __int128
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppp pair<pii,pii>
#define deb cerr<<"Arknights AK IOI\n"
#define tostring(a) #a
#define cono(a,b) a##b
#define psa(i) (i=-~(i))
#define range(i) (-~(i))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read()
{
ll s=0;int w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^'0'),ch=getchar();
return s*w;
}
void IO()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
const int N=1e5+10;const ll MAXMOD=1e13+37;
int n,block_len,a[N],len,t,block[N],ans[N],cnt[N];
ll cur,lg[N];
struct Query
{
int l,r,p,idx;
bool operator <(const Query p)const
{
if(block[l] xor block[p.l])return l<p.l;
if(block[l]&1)return r<p.r;
return r>p.r;
}
}q[N];
inline ll qpow(int a,int p,int MOD)
{
ll res=1;
while(p)
{
if(p&1)res=res*a%MOD;
a=a*a%MOD;p>>=1;
}
return res;
}
inline void build()
{
block_len=pow(n,2.0/3.0);
for(int i=1;i<=block_len;psa(i))block[i]=1;
for(int i=block_len+1;i<=n;psa(i))
block[i]=block[i-block_len]+1;
}
inline void add(int pnt,ll MOD=MAXMOD)
{
cur<<=1;
if(!cnt[a[pnt]])cur=(cur+lg[len]*a[pnt])%MOD;
else cur=(cur+lg[len-cnt[a[pnt]]]*a[pnt])%MOD;
psa(cnt[a[pnt]]);psa(len);
}
inline void del(int pnt,ll MOD=MAXMOD)
{
--cnt[a[pnt]];--len;
if(!cnt[a[pnt]])cur-=lg[len]*a[pnt];
else cur-=lg[len-cnt[a[pnt]]]*a[pnt];
if(cur<=0)cur+=MOD;cur>>=1;
}
int main()
{
n=read(),t=read();
build();lg[0]=1;
for(int i=1;i<=n;psa(i))a[i]=read(),lg[i]=(lg[i-1]<<1)%MAXMOD;
for(int i=1;i<=t;psa(i))
{
int l=read(),r=read(),p=read();
q[i]=(Query){l,r,p,i};
}
sort(q+1,q+1+t);
// deb;
for(int l=1,r=0,i=1;i<=t;psa(i))
{
while(l>q[i].l)add(--l);
// cerr<<cur<<endl;
while(l<q[i].l)del(l++);
// cerr<<cur<<endl;
while(r>q[i].r)del(r--);
// cerr<<cur<<endl;
while(r<q[i].r)add(++r);
// cerr<<cur<<endl;
ans[q[i].idx]=cur%q[i].p;
// cerr<<q[i].idx<<": l:"<<q[i].l<<" r:"<<q[i].r<<" cur:"<<cur<<endl;
}
for(int i=1;i<=t;psa(i))printf("%d\n",ans[i]);
Arknights AK IOI
}
```
by ReturnOrContinue @ 2024-02-22 15:06:57
@[ReturnOrContinue](/user/767588) 做法假了吧/yun
by h_rains @ 2024-02-22 16:10:09
@[h_rains](/user/665801) 我试过标记MOD的数量，但是__int128都能爆，我都放弃了。我试试用链表吧
by ReturnOrContinue @ 2024-02-22 16:22:19
@[ReturnOrContinue](/user/767588) 你思路啥
by mashduihca @ 2024-02-23 17:24:14