首页 > 代码库 > BZOJ2482: [Spoj1557] Can you answer these queries II
BZOJ2482: [Spoj1557] Can you answer these queries II
题解：
从没见过这么XXX的线段树啊。。。
T_T
我们考虑离线做，按1-n一个一个插入，并且维护区间【 j，i】（i为当前插入的数）j<i的最优值。
但这个最优值！！！
我们要保存历史的最优值，以及当前的最优值！！！还有lazy！！！也得分历史和现在！！T_T
怎么搞！！！
inline void update(int k,int z1,int z2){ t[k].tag[1]=max(t[k].tag[1],t[k].tag[0]+z2); t[k].tag[0]+=z1; t[k].mx[1]=max(t[k].mx[1],t[k].mx[0]+z2); t[k].mx[0]+=z1; t[k].mx[1]=max(t[k].mx[1],t[k].mx[0]);}inline void pushdown(int k){ if(!t[k].tag[0]&&!t[k].tag[1])return; update(k<<1,t[k].tag[0],t[k].tag[1]); update(k<<1|1,t[k].tag[0],t[k].tag[1]); t[k].tag[0]=t[k].tag[1]=0;}
就是这么鬼畜，然后剩下的套模板就好了。。。
其实也蛮好理解的。
tag[0]表示从上次pushdown到现在加了多少
tag[1]表示从上次pushdown到现在tag[0]最多达到过多少，因为祖先的操作可能累计了很多次，我们只需要向下传一下最大的。
mx[0]和mx[1]与tag类似。
对拍了一组数据发现RE了，调了1h发现我dtmk写错了！！！说多了都是泪啊T_T
不过#2还是蛮开心的 哈哈~
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 200000+5 14 #define maxm 100000+5 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27 int x=0,f=1;char ch=getchar(); 28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30 return x*f; 31 } 32 int n,m,v[maxn],last[maxn],ans[maxn]; 33 struct rec{int l,r,id;}a[maxn]; 34 inline bool cmp(rec x,rec y){return x.r<y.r;} 35 struct seg{int l,r,mx[2],tag[2];}t[4*maxn]; 36 inline void build(int k,int l,int r) 37 { 38 t[k].l=l;t[k].r=r;int mid=(l+r)>>1; 39 if(l==r)return; 40 build(k<<1,l,mid);build(k<<1|1,mid+1,r); 41 } 42 inline void update(int k,int z1,int z2) 43 { 44 t[k].tag[1]=max(t[k].tag[1],t[k].tag[0]+z2); 45 t[k].tag[0]+=z1; 46 t[k].mx[1]=max(t[k].mx[1],t[k].mx[0]+z2); 47 t[k].mx[0]+=z1; 48 t[k].mx[1]=max(t[k].mx[1],t[k].mx[0]); 49 } 50 inline void pushup(int k) 51 { 52 for0(i,1)t[k].mx[i]=max(t[k<<1].mx[i],t[k<<1|1].mx[i]); 53 } 54 inline void pushdown(int k) 55 { 56 if(!t[k].tag[0]&&!t[k].tag[1])return; 57 update(k<<1,t[k].tag[0],t[k].tag[1]); 58 update(k<<1|1,t[k].tag[0],t[k].tag[1]); 59 t[k].tag[0]=t[k].tag[1]=0; 60 } 61 inline void add(int k,int x,int y,int z) 62 { 63 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 64 if(l==x&&r==y){update(k,z,0);return;} 65 pushdown(k); 66 if(y<=mid)add(k<<1,x,y,z); 67 else if(x>mid)add(k<<1|1,x,y,z); 68 else add(k<<1,x,mid,z),add(k<<1|1,mid+1,y,z); 69 pushup(k); 70 } 71 inline int query(int k,int x,int y) 72 { 73 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 74 if(l==x&&r==y)return t[k].mx[1]; 75 pushdown(k); 76 if(y<=mid)return query(k<<1,x,y); 77 else if(x>mid)return query(k<<1|1,x,y); 78 else return max(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); 79 } 80 #define last(i) last[100000+i] 81 int main() 82 { 83 freopen("input.txt","r",stdin); 84 freopen("output.txt","w",stdout); 85 n=read(); 86 for1(i,n)v[i]=read(); 87 build(1,1,n); 88 m=read(); 89 for1(i,m)a[i].l=read(),a[i].r=read(),a[i].id=i; 90 sort(a+1,a+m+1,cmp); 91 int j=1; 92 for1(i,n) 93 { 94 int tmp=last(v[i]);last(v[i])=i; 95 add(1,tmp+1,i,v[i]); 96 while(a[j].r==i)ans[a[j].id]=query(1,a[j].l,i),j++; 97 } 98 for1(i,m)printf("%d\n",ans[i]); 99 return 0;100 }
2482: [Spoj1557] Can you answer these queries II
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 115 Solved: 67
[Submit][Status]
Description
给定n个元素的序列。
给出m个询问：求l[i]~r[i]的最大子段和（可选空子段）。
这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。
比如：1，2，3，2，2，2出现了3次，但只算一次，于是这个序列的和是1+2+3=6。
Input
第一行一个数n。
第二行n个数，为给定的序列，这些数的绝对值小于等于100000。
第三行一个数m。
接下来m行，每行两个数，l[i]，r[i]。
Output
M行，每行一个数，为每个询问的答案。
Sample Input
9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
Sample Output
4
5
3
HINT
【数据说明】
30%：1 <= n, m <= 100
100%：1 <= n, m <= 100000
Source
spoj gss2
BZOJ2482: [Spoj1557] Can you answer these queries II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。