SPOJ GSS2 Can you answer these queries II

SPOJ GSS2 Can you answer these queries II"/>

SPOJ GSS2 Can you answer these queries II

很好的一道题，想了很久。首先突破的是，可以找到枚举其中一边，假设是尾部y，然后快速找出满足条件的最大的头部x，连续区间的和

很容易想到借助部分和的思想，如果是从y开始往前面累加，那么就是一个关于y的后缀和。

如果答案的一边在y，那么就转化成了对后缀和的RMQ。

y的后缀和y-1或者y+1的后缀是差不多的，只要想想怎么递推就好了。

y == 0时的所有后缀是很容易得到的，因此考虑用y递推y+1，这个后缀和是从右边往左累加的，重复的不算，

对于元素a[y+1]，它所影响的后缀只有y+1到a[y+1]上一次出现的位置，区间更新就好了。

然后就卡了，经过鼠宝宝提醒才想到，在上面过程中可以再维护一个历史最值，这个历史最值怎么维护也是各种纠结。。。

最容易想到的是在线段树区间更新的时候，当前max改变的时候用来更新历史最值，但是因为是区间更新，需要打标记，

而打上标记的子节点的历史最值实际上没有更新到，因此对于历史最值的更新也打上一个标记。

/*********************************************************
*            ------------------                          *
*   author AbyssalFish                                   *
**********************************************************/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;typedef long long ll;
const int MAX_N = 1e5+5;int dat[MAX_N*2];
int *const ps = dat + MAX_N;
int a[MAX_N];const int MAX_M = MAX_N;template<typename T>
struct LIST
{int hd[MAX_N];int nx[MAX_M];T val[MAX_M];int sz;void init(int n){memset(hd+1,0,sizeof(int)*n); sz = 0;}void add(int u, const T &v){nx[++sz] = hd[u];val[sz] = v;hd[u] = sz;}
};LIST<int> lyx;int N;#define para int o = 1, int l = 1, int r = N
#define lo (o<<1)
#define ro (o<<1|1)
#define Tvar int md = (l+r)>>1;
#define lsn lo,l,md
#define rsn ro,md+1,r
#define insd ql<=l&&r<=qrconst int ST_SIZE = 1<<18;ll dwn[ST_SIZE];
ll mx[ST_SIZE];
ll his_mx[ST_SIZE];
ll his_dwn[ST_SIZE];inline void sink_his(int o, ll d)
{his_dwn[o] = max(his_dwn[o], dwn[o] + d);//历史最值更新的标记也是取最大的his_mx[o] = max(his_mx[o], mx[o] + d);
}inline void sink(int o,ll d)
{mx[o] += d;dwn[o] += d;
}inline void push_down(int o)
{ll &d = his_dwn[o];if(d){ //子节点还没更新，保存的是旧值
        sink_his(lo,d);sink_his(ro,d);d = 0;}ll &d2 = dwn[o];if(d2){sink(lo,d2);sink(ro,d2);d2 = 0;}
}int ql,qr;
ll q_dlt;
void modify(para)
{if(insd){sink(o,q_dlt);his_dwn[o] = max(his_dwn[o], dwn[o]);his_mx[o] = max(his_mx[o], mx[o]);}else {Tvarpush_down(o);if(ql <= md) modify(lsn);if(qr > md) modify(rsn);mx[o] = max(mx[lo],mx[ro]);his_mx[o] = max(mx[o], his_mx[o]);}
}ll q_his_mx(para)
{if(insd) return his_mx[o];else {Tvarpush_down(o);ll re = -INFINITY;if(ql <= md) re = max(re,q_his_mx(lsn));if(qr > md) re = max(re,q_his_mx(rsn));return re;}
}ll ans[MAX_N];void solve()
{int i;for(i = 1; i <= N; i++){scanf("%d", a+i);}int Q; scanf("%d",&Q);int x, y;for(i = 1; i <= Q; i++){scanf("%d%d",&x, &y);lyx.add(y,x);}for(y = 1; y <= N; y++){ql = ps[a[y]]+1;qr = y;q_dlt = a[y];ps[a[y]] = y;modify();for(i = lyx.hd[y]; i; i = lyx.nx[i]){ql = lyx.val[i];ans[i] = q_his_mx();}}for(i = 1; i <= Q; i++){printf("%lld\n", ans[i]);}
}//#define LOCAL
int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endif//cout<<(((int)ceil(log2(MAX_N))+1))<<endl;scanf("%d",&N);solve();return 0;
}

转载于:.html