题目描述
给定长度nn的序列ss。
qq第二次询问，每一次询问像a b c d e f，您需要找出以下公式的值：
\sum_{L=a}^{b}[e\le G(F(L,c),F(L,c 1),\cdots,F(L,d))\le f]L=a∑b[e≤G(F(L,c),F(L,c 1),?,F(L,d))≤f]
这里F(l,r)F(l,r)表示ss序列区间[l,r][l,r]不同数量的数量，G(x_1,x_2,\cdots,x_k)G(x1,x2,?,xk)表示x_1,x_2,\cdots,x_kx1,x2,?,xk数量不同。
输入格式
第一行有两个整数n,qn,q，表示序列长度和命令次数。
第二行输入nn个整数，第ii个数表示s_isi。
下面qq行，每行输入66个数a',b',c',d',e,fa′,b′,c′,d′,e,f。上次提出的答案是\text{lastans}lastans（特别的，若这是第一次询问，则\text{lastans}=0lastans=0)，在这次询问中
a=(a' \text{lastans})\bmod n 1\\a=(a′ lastans)modn 1b=(b' \text{lastans})\bmod n 1\\b=(b′ lastans)modn 1c=(c' \text{lastans})\bmod n 1\\c=(c′ lastans)modn 1d=(d' \text{lastans})\bmod n 1\\d=(d′ lastans)modn 1
输出格式
依次输出答案次输出答案。
输入输出样例
复制
3 1 2020 2021 2020 3 3 2 2 1 1
复制
1
复制
10 3 2 2 4 3 5 3 5 4 1 2 3 5 2 4 1 2 5 7 2 9 2 4 1 3 1 8 1 3
复制
2 4 4
说明/提示
【样例一解释】
在第一次询问中，a=1,b=1,c=3,d=3,e=1,f=1a=1,b=1,c=3,d=3,e=1,f=1。
不难得到G(F(1,3))=1G(F(1,3))=1，且e\le G(F(1,3))\le fe≤G(F(1,3))≤f，所以答案为11。
【样例二解释】
| 询问编号 | aa | bb | cc | dd | ee | ff |
|---|---|---|---|---|---|---|
| ① | 3 | 4 | 5 | 6 | 1 | 2 |
| ② | 2 | 5 | 8 | 10 | 2 | 4 |
| ③ | 3 | 6 | 6 | 8 | 1 | 3 |
| 数据范围 |
。
- Subtask1（10pts）：n,q\le500n,q≤500，1\le s_i\le10^61≤si≤106；
- Subtask2（15pts）：n,q\le3\times10^3n,q≤3×103；
- Subtask3（20pts）：b-a\le20b?a≤20；
- Subtask4（25pts）：n,q\le10^5n,q≤105；
- Subtask5（30pts）：没有特殊限制。
对于100\0%数据满足，1\le n,q\le3\times10^51≤n,q≤3×105，0\le|s_i|\le10^90≤∣si∣≤对于所有的询问，109\le a,b,c,d\le n1≤a,b,c,d≤n，0\le e\le f\le n0≤e≤f≤n。
【提示】
-
本题中，[x \le y \le z][x≤y≤z]表示yy是否\in[x,z]∈[x,z]。如果在此范围内，则值为11；否则为00。
-
输入量大，请快速读入。
上代码：
#include<bits/stdc .h> using namespace std; const int Maxn=3e5; inline int read() { char ch=getchar(); int f=1,x=0; while(ch>'9' || ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9') { x=x*10 ch-'0'; ch=getchar(); } return x*f; } struct Node{int l,r,siz;} t[Maxn*40 5]; int tot,rt[Maxn 5]; #define ls(x) t[x].l #define rs(x) t[x].r int n,m,lst,h[Maxn 5],cnt[Maxn 5],nxt[Maxn 5],Q[10]; vector<int> v; inline void Insert(int l,int r,int L,int &R,int val) { t[ tot]=t[L],R=tot,t[R].siz ; if(l==r) return; int mid=(l r)>>1; if(val<=mid) Insert(l,mid,ls(L),ls(R),val); else Insert(mid 1,r,rs(L),rs(R),val); } inline int Find(int l,int r,int L,int R,int val) { if(l==r) return t[R].siz-t[L].siz; int mid=(l r)>>1; if(val<=mid) return t[rs(R)].siz-t[rs(L)].siz Find(l,mid,ls(L),ls(R),val); else return Find(mid 1,r,rs(L),rs(R),val); } inline int F(int l,int r) {return Find(1,n 1,rt[l-1],rt[r],r 1);} inline void Solve() { while(m--) { int a,b,c,d,e,f,l,r,siz=-1; for(int i=1;i<=4; i) Q[i]=(read() lst)%n 1; sort(Q 1,Q 5),a=Q[1],b=Q[2],c=Q[3],d=Q[4],e=read(),f=read(),l=a-1,r=b; while(l<r) { int mid=(l r 1)/2; if(mid==a-1 || F(mid,d)-F(mid,c) 1<e) l=mid; else r=mid-1; } siz-=l,l=a,r=b 1; while(l<r) { int mid=(l r)/2; if(mid==b 1 || F(mid,d)-F(mid,c) 1>f) r=mid; else l=mid 1; } siz =l,lst=siz; printf("%d\n",siz); } } inline void Init() { n=read(),m=read(); for(int i=1;i<=n; i) v.push_back(h[i]=read()),cnt[i]=n 1; sort(v.begin(),v.end()),v.erase(unique(v.begn(),v.end()),v.end());
for(int i=1;i<=n;++i) h[i]=lower_bound(v.begin(),v.end(),h[i])-v.begin()+1;
for(int i=n;i>=1;--i) nxt[i]=cnt[h[i]],cnt[h[i]]=i;
for(int i=1;i<=n;++i) Insert(1,n+1,rt[i-1],rt[i],nxt[i]);
}
int main()
{
Init(),Solve();
return 0;
}