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; }
Terrific work! This is the kind of info that are supposed to be shared across the web.
Disgrace on Google for no longer positioning this submit higher!
Come on over and seek advice from my website . Thank you =)