分类表里最后一道线段树了。
题意大概是：有一个环，环上有N个整数，求在每次更新环上某个值后，环（除整个环外）任意弧上最大的整数和。
乍看下去，虽然提示是用线段树，但还是想了很久也没思路。再看了下输入规模，N最大10^5，更新次数M也是10^5，于是单次更新的处理时间只能是O(lgN)的。这样便能看出来是每次更新都在线段树上作O(lgN)深度的线段信息更新，再由根结点信息得到结果。
这里由左右子结点得到父结点信息的题推关系还是挺麻烦的……要考虑左连续区间最值和对应的最右元素位置，右连续区间最值和对应的最左元素位置，以及区间中任意子连续区间上的最值，再加上区间上全部整数和，总共是6个量。
这里要记录左右最值区间对应边界位置是因为，最后在根结点处计算时是可以将最右和最左看作连续的（环的性质），这样如果子结点上左右区间有重叠时，直接相加便会出错了，因此记录边界便能在仅当左右区间不重叠时才计算值。
另外这题要求不能取整个环上所有元素，因此实际上求的是最小弧，再用全部整数和减去最小值便能得到最大弧了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<cstdio> #include<cstring> int n,m,d[100000],ml; struct node { int s,ld,rd,md,lr,rl; node *l,*r; }mem[200000],*root; void ins(int L,int R,node *p,int i=-1) { int m=L+R>>1; if(L==R) { p->s=d[m]; p->ld=p->rd=p->md=d[m]; p->lr=p->rl=m; return; } if(i==-1) { p->l=&mem[ml++]; p->r=&mem[ml++]; ins(L,m,p->l); ins(m+1,R,p->r); } else if(i<=m) ins(L,m,p->l,i); else ins(m+1,R,p->r,i); p->s=p->l->s+p->r->s; if(p->l->ld<=p->l->s+p->r->ld) { p->ld=p->l->ld; p->lr=p->l->lr; } else { p->ld=p->l->s+p->r->ld; p->lr=p->r->lr; } if(p->r->rd<=p->r->s+p->l->rd) { p->rd=p->r->rd; p->rl=p->r->rl; } else { p->rd=p->r->s+p->l->rd; p->rl=p->l->rl; } p->md=p->l->rd+p->r->ld; p->md=p->md<p->l->md?p->md:p->l->md; p->md=p->md<p->r->md?p->md:p->r->md; } inline int calc(int i) { ins(0,n-1,root,i); int e=root->md,m=n-1>>1; e=e<root->l->ld+root->r->rd?e:root->l->ld+root->r->rd; if(root->r->lr<root->r->rl) e=e<root->l->s+root->r->ld+root->r->rd?e:root->l->s+root->r->ld+root->r->rd; if(root->l->lr<root->l->rl) e=e<root->r->s+root->l->ld+root->l->rd?e:root->r->s+root->l->ld+root->l->rd; return root->s-e; } int main() { int i,j; while(~scanf("%d",&n)) { ml=0; root=&mem[ml++]; for(i=0;i<n;i++) scanf("%d",&d[i]); scanf("%d",&m); ins(0,n-1,root); while(m--) { scanf("%d%d",&i,&j); d[i-1]=j; printf("%d\n",calc(i-1)); } } return 0; } |