首页 > 代码库 > cogs775 山海经 线段树
cogs775 山海经 线段树
链接：http://cogs.pro/cogs/problem/problem.php?pid=775
题意：维护区间最大值及其最小字典序来源。
细节巨多……多的狗死人了……
首先我们要建出一棵线段树，这棵线段树要存放以下几个东西：最长区间，起点，终点，最长前缀，前缀终点，最长后缀，后缀起点。（所以维护打了足足六十行……查询打了三十行……）
如何查询呢？最长序列无外乎三种情况：
1、全在左子树中。我们设$len[i]$为$i$节点最长序列，则此时$len[i]=len[i<<1]$；
2、全在右子树中，同理可以得出$len[i]=len[i<<1|1]$。
3、横跨两个子树。设前缀长为$pre[i]$，后缀长为$suf[i]$，那么$len[i]=suf[i<<1]+pre[i<<1|1]$。
维护时顺带按照长度第一字典序第二要求维护区间起终点即可。
查询时按照相同方法进行查询，需要注意的是，最后一次合并时左右可能并未完全更新，上传完成后还要再找一次最优解。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int maxn=100005,inf=0x3f3f3f3f; 7 struct node 8 { 9 int l,r,lmax,rmax,st,en,totmax,pre,suf,sum; 10 node() 11 { 12 lmax=rmax=totmax=-inf;sum=0; 13 } 14 }segtree[maxn<<2]; 15 #define mid ((l+r)>>1) 16 #define lc root<<1 17 #define rc root<<1|1 18 #define lson lc,l,mid 19 #define rson rc,mid+1,r 20 void pushup(int root) 21 { 22 segtree[root].sum=segtree[lc].sum+segtree[rc].sum; 23 if(segtree[lc].lmax<segtree[lc].sum+segtree[rc].lmax) 24 { 25 segtree[root].lmax=segtree[lc].sum+segtree[rc].lmax; 26 segtree[root].pre=segtree[rc].pre; 27 } 28 else 29 { 30 segtree[root].lmax=segtree[lc].lmax; 31 segtree[root].pre=segtree[lc].pre; 32 } 33 if(segtree[rc].rmax<segtree[rc].sum+segtree[lc].rmax) 34 { 35 segtree[root].rmax=segtree[rc].sum+segtree[lc].rmax; 36 segtree[root].suf=segtree[lc].suf; 37 } 38 else 39 { 40 segtree[root].rmax=segtree[rc].rmax; 41 segtree[root].suf=segtree[rc].suf; 42 } 43 if(segtree[lc].totmax<segtree[rc].totmax) 44 { 45 if(segtree[rc].totmax<=segtree[lc].rmax+segtree[rc].lmax) 46 { 47 segtree[root].totmax=segtree[lc].rmax+segtree[rc].lmax; 48 segtree[root].st=segtree[lc].suf; 49 segtree[root].en=segtree[rc].pre; 50 } 51 else 52 { 53 segtree[root].totmax=segtree[rc].totmax; 54 segtree[root].st=segtree[rc].st; 55 segtree[root].en=segtree[rc].en; 56 } 57 } 58 else if(segtree[lc].totmax<segtree[lc].rmax+segtree[rc].lmax) 59 { 60 segtree[root].totmax=segtree[lc].rmax+segtree[rc].lmax; 61 segtree[root].st=segtree[lc].suf; 62 segtree[root].en=segtree[rc].pre; 63 } 64 else if(segtree[lc].totmax==segtree[lc].rmax+segtree[rc].lmax) 65 { 66 segtree[root].totmax=segtree[lc].totmax; 67 if(segtree[lc].st>segtree[lc].suf) 68 { 69 segtree[root].st=segtree[lc].suf; 70 segtree[root].en=segtree[rc].pre; 71 } 72 else 73 { 74 segtree[root].st=segtree[lc].st; 75 segtree[root].en=segtree[root].en; 76 } 77 } 78 else 79 { 80 segtree[root].totmax=segtree[lc].totmax; 81 segtree[root].st=segtree[lc].st; 82 segtree[root].en=segtree[lc].en; 83 } 84 } 85 void cmp(node x,node y,node &z) 86 { 87 z.l=x.l,z.r=y.r;z.sum=x.sum+y.sum; 88 if(x.lmax<x.sum+y.lmax) 89 { 90 z.lmax=x.sum+y.lmax; 91 z.pre=y.pre; 92 } 93 else z.lmax=x.lmax,z.pre=x.pre; 94 if(y.rmax<y.sum+x.rmax) 95 { 96 z.rmax=y.sum+x.rmax; 97 z.suf=x.suf; 98 } 99 else 100 { 101 z.rmax=y.rmax; 102 z.suf=y.suf; 103 } 104 if(x.totmax<y.totmax) 105 { 106 if(y.totmax<=x.rmax+y.lmax) 107 { 108 z.totmax=x.rmax+y.lmax; 109 z.st=x.suf; 110 z.en=y.pre; 111 } 112 else 113 { 114 z.totmax=y.totmax; 115 z.st=y.st; 116 z.en=y.en; 117 } 118 } 119 else if(x.totmax<x.rmax+y.lmax) 120 { 121 z.totmax=x.rmax+y.lmax; 122 z.st=x.suf; 123 z.en=y.pre; 124 } 125 else if(x.totmax==x.rmax+y.lmax) 126 { 127 z.totmax=x.totmax; 128 if(x.suf<x.st)z.st=x.suf,z.en=y.pre; 129 else z.st=x.st,z.en=x.en; 130 } 131 else z.totmax=x.totmax,z.st=x.st,z.en=x.en; 132 } 133 void build(int root,int l,int r) 134 { 135 segtree[root].l=l,segtree[root].r=r; 136 if(l==r) 137 { 138 int tmp;scanf("%d",&tmp); 139 segtree[root].sum=segtree[root].lmax=segtree[root].rmax=segtree[root].totmax=tmp; 140 segtree[root].st=segtree[root].en=segtree[root].pre=segtree[root].suf=l; 141 return; 142 } 143 build(lson),build(rson); 144 pushup(root); 145 } 146 #undef mid 147 void print(node t) 148 { 149 if(t.lmax>=t.rmax) 150 if(t.lmax>=t.totmax)printf("%d %d %d\n",t.l,t.pre,t.lmax); 151 else printf("%d %d %d\n",t.st,t.en,t.totmax); 152 else if(t.rmax>t.totmax)printf("%d %d %d\n",t.suf,t.r,t.rmax); 153 else printf("%d %d %d\n",t.st,t.en,t.totmax); 154 } 155 node query(int root,int l,int r) 156 { 157 if(segtree[root].l>=l&&segtree[root].r<=r) 158 return segtree[root]; 159 int mid=segtree[root].l+segtree[root].r>>1;node t1,t2,t3; 160 if(l<=mid)t1=query(lc,l,r);if(r>mid)t2=query(rc,l,r); 161 t1.l=l,t1.r=mid,t2.l=mid+1,t2.r=r; 162 cmp(t1,t2,t3);return t3; 163 } 164 int n,q; 165 int haha() 166 { 167 freopen("hill.in","r",stdin); 168 freopen("hill.out","w",stdout); 169 scanf("%d%d",&n,&q); 170 build(1,1,n); 171 for(int i=1;i<=q;i++) 172 { 173 int x,y;scanf("%d%d",&x,&y); 174 node t=query(1,x,y); 175 print(t); 176 } 177 } 178 int sb=haha(); 179 int main(){;}
.
cogs775 山海经 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。