JOISC2014 Day1 T3。回滚莫队例题。
题目链接:JOISC2014 D1T3、LOJ 2874。
未完待续
题目
题目描述
IOI 国历史研究的大牛——JOI 教授,最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活,开始着手调查日记中记载的事件。
日记中记录了连续 天发生的事件,每天发生一件事件。
事件有种类之分。第 \(N\) 天发生的事件的种类用一个整数 \(X _ i\) 表示,\(X _ i\) 越大,事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记:
- 选择日记中连续的一些天作为分析的时间段;
- 事件种类 \(t\) 的重要度为 \(t\) 与这段时间内重要度为 \(t\) 的事件数的乘积;
- 计算出所有事件种类的重要度,输出其中的最大值。
请制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。
数据范围
子任务编号 | 分值 | 附加条件 |
1 | 5 | \(N,Q\leq 100\) |
2 | 10 | \(N,Q\leq 5000\) |
3 | 25 | 没有 \(i,j(1\leq i\leq Q,1\leq j\leq Q,i\ne j)\),使得 \(A _ i\leq A _ j\leq B _ j\leq B _ i\)。 |
4 | 60 | 无 |
时空限制
题解
思路
回滚莫队板子题。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=1e5+5; const int MAXSQRTN=317+5; //\sqrt{n} 的最大值 const int MAXQ=1e5+5; int n,q; int a[MAXN]; int pos[MAXN]; //所在块的编号 int L[MAXSQRTN],R[MAXSQRTN]; //各个块的左右端点 struct querys{ int l,r,id; inline querys(reg int l=0,reg int r=0,reg int id=0):l(l),r(r),id(id){ return; } inline bool operator<(const querys& a)const{ //排序 if(pos[l]!=pos[a.l]) return l<a.l; return r<a.r; } }; querys Q[MAXQ]; inline void build(void){ //初始化块信息 reg int size=sqrt(n); reg int tot=n/size; for(reg int i=1;i<=tot;++i){ L[i]=(i-1)*size+1; R[i]=i*size; } if(R[tot]<n){ ++tot; R[tot]=n; L[tot]=R[tot-1]+1; } for(reg int i=1;i<=tot;++i) for(reg int j=L[i];j<=R[i];++j) pos[j]=i; return; } vector<int> V; int __cnt[MAXN]; //该数组用于块内暴力求解 int T[MAXN]; //桶 ll ans[MAXQ]; inline void add(reg int x,reg ll &ans){ ++T[x]; ans=max(ans,1ll*V[x-1]*T[x]); //统计答案 return; } inline void del(reg int x){ --T[x]; return; } int main(void){ n=read(),q=read(); build(); for(reg int i=1;i<=n;++i){ a[i]=read(); V.push_back(a[i]); } sort(V.begin(),V.end()); V.erase(unique(V.begin(),V.end()),V.end()); for(reg int i=1;i<=n;++i) a[i]=lower_bound(V.begin(),V.end(),a[i])-V.begin()+1; for(reg int i=1;i<=q;++i){ static int l,r; l=read(),r=read(); Q[i]=querys(l,r,i); } sort(Q+1,Q+q+1); reg int l=1,r=0; ll Ans=0,tmp; int LastB=0; for(reg int i=1;i<=q;++i){ if(pos[Q[i].l]==pos[Q[i].r]){ //块内暴力 ll Ans=0; for(reg int j=Q[i].l;j<=Q[i].r;++j){ ++__cnt[a[j]]; Ans=max(Ans,1ll*V[a[j]-1]*__cnt[a[j]]); } for(reg int j=Q[i].l;j<=Q[i].r;++j) --__cnt[a[j]]; ans[Q[i].id]=Ans; continue; } if(pos[Q[i].l]!=LastB){ //块编号不同,删除信息 while(r>R[pos[Q[i].l]]) del(a[r--]); while(l<R[pos[Q[i].l]]+1) del(a[l++]); Ans=0; LastB=pos[Q[i].l]; } while(r<Q[i].r) add(a[++r],Ans); reg int __l=l; tmp=Ans; while(__l>Q[i].l) add(a[--__l],tmp); ans[Q[i].id]=tmp; while(__l<l) //回滚 del(a[__l++]); } for(reg int i=1;i<=q;++i) printf("%lld\n",ans[i]); return 0; }
近期评论