Description

IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。

日记中记录了连续N天发生的时间，大约每天发生一件。

事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。

JOI教授决定用如下的方法分析这些日记：

1. 选择日记中连续的一些天作为分析的时间段

2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)

3. 计算出所有事件种类的重要度，输出其中的最大值

现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

Solution

回滚莫队。。。

有些时候，增加操作是不可逆的，就比如说求最值什么的

对于左端点所在的块相同的询问，它们右端点单增

而左边，你只需要让left停留在这个块的最右边

每次暴力往左推，但不更新ans，这样就可以避免删除了

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 100005int n,m,T,a[MN],R[1005];struct ques{    int l,r,pl,pr,id;    bool operator <(const ques &o) const {return (pl^o.pl)?(pl
     
      
       q[i].l;--l) tmp<1ll*(++num[a[l-1]])*fnum[a[l-1]]?tmp=1ll*num[a[l-1]]*fnum[a[l-1]]:0;            for(;l
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！