SP1557 GSS2 - Can you answer these queries II

题面传送门
题目中怎么不说明这个可以取空区间啊害我调半天。
这个重复的算一次就容易想到区间数颜色的相关套路，就是每个点记录前面最近的点。
离线询问然后扫描线，记录线段树上每个位置的值为到当前点的区间的和，那么需要做的就是两种操作：
将上一个这个数的出现位置+1到现在的位置都加上一个数。
查询区间历史最值。
历史最值有基本套路，新加一个权值\(F_i\)表示\(i\)位置的历史最值，那么每次扫描完一个数以后就对于全序列让\(F_i=\max(F_i,A_i)\)
这个维护一个标记，再配合一个位移标记就可以和加法相容了。
时间复杂度线段树的\(O(n\log n)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N (100000+5)
#define M (1000000+5)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;const ll INF=1e18;
int n,m,k,x,y;ll Ans[N],A[N];map F;struct Ques{int x,id;};vector Q[N+5];
namespace Tree{
	#define ls now<<1
	#define rs now<<1|1
	int Fl[N+5<<2];ll W[N+5<<2],G[N+5<<2],F[N+5<<2],H[N+5<<2];I void Up(int now){F[now]=max(F[ls],F[rs]);G[now]=max(G[ls],G[rs]);}
	I void PL(int now,ll w){Fl[now]?(W[now]=max(W[now],w)):(Fl[now]=1,W[now]=w);G[now]=max(G[now],F[now]+W[now]);}I void PH(int now,ll w){H[now]+=w;F[now]+=w;Fl[now]&&(W[now]-=w);}
	I void P(int now){H[now]&&(PH(ls,H[now]),PH(rs,H[now]),H[now]=0);Fl[now]&&(PL(ls,W[now]),PL(rs,W[now]),Fl[now]=W[now]=0);}
	I ll Qry(int x,int y,int l=1,int r=n,int now=1){if(x<=l&&r<=y) return G[now];P(now);int m=l+r>>1;ll F1=-INF,F2=-INF;x<=m&&(F1=Qry(x,y,l,m,ls));y>m&&(F2=Qry(x,y,m+1,r,rs));return max(F1,F2);}
	I void Ins(int x,int y,ll w,int l=1,int r=n,int now=1){if(x<=l&&r<=y) return PH(now,w);int m=l+r>>1;P(now);x<=m&&(Ins(x,y,w,l,m,ls),0);y>m&&(Ins(x,y,w,m+1,r,rs),0);Up(now);}
	I void Add(int x,int y,int l=1,int r=n,int now=1){if(x<=l&&r<=y) return PL(now,0);int m=l+r>>1;P(now);x<=m&&(Add(x,y,l,m,ls),0);y>m&&(Add(x,y,m+1,r,rs),0);Up(now);}
}
int main(){
	freopen("1.in","r",stdin);
	RI i;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%lld",&A[i]);scanf("%d",&m);for(i=1;i<=m;i++) scanf("%d%d",&x,&y),Q[y].PB((Ques){x,i});
	for(i=1;i<=n;i++) {Tree::Ins(F[A[i]]+1,i,A[i]);F[A[i]]=i;Tree::Add(1,n);for(Ques d:Q[i]) Ans[d.id]=Tree::Qry(d.x,i);}for(i=1;i<=m;i++) printf("%lld\n",Ans[i]);
}