Training address: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38994#overview
B.Xenia and Bit Operations ----Codeforces 339D
线段树大水题。。每个节点维护一个flag，flag=1表示此时应与其兄弟节点做或（|）操作，flag=2表示做异或（^）操作，然后pushup...
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 140010 struct node
{
int sum,flag;
}tree[*N]; int two_n(int mi)
{
int i;
int res = ;
for(i=;i<=mi;i++)
{
res *= ;
}
return res;
} int a[N]; void pushup(int rt)
{
if(tree[*rt].flag == )
{
tree[rt].sum = tree[*rt].sum | tree[*rt+].sum;
tree[rt].flag = ;
}
else
{
tree[rt].sum = tree[*rt].sum ^ tree[*rt+].sum;
tree[rt].flag = ;
}
} void build(int l,int r,int rt)
{
if(l == r)
{
tree[rt].sum = a[l];
tree[rt].flag = ;
return;
}
int mid = (l+r)/;
build(l,mid,*rt);
build(mid+,r,*rt+);
pushup(rt);
} void update(int l,int r,int pos,int val,int rt)
{
if(l == r)
{
tree[rt].sum = val;
tree[rt].flag = ;
return;
}
int mid = (l+r)/;
if(pos<=mid)
update(l,mid,pos,val,*rt);
else
update(mid+,r,pos,val,*rt+);
pushup(rt);
} int main()
{
int n,m;
int i,pos,val;
while(scanf("%d%d",&n,&m)!=EOF)
{
int ken = two_n(n);
for(i=;i<=ken;i++)
{
scanf("%d",&a[i]);
}
build(,ken,);
for(i=;i<m;i++)
{
scanf("%d%d",&pos,&val);
update(,ken,pos,val,);
printf("%d\n",tree[].sum);
}
}
return ;
}
D.Copying Data ----Codeforces 292E
这题初看像线段树题，结果就是线段树题。怎么做树，维护哪些值呢？ 开始想歪了，参照了别人的报告，于是知道，可以维护stx,sty值，这些值只在叶子节点上表现出来，因为只查叶子节点，不查区间，stx记录这个节点有没有被copy成a数组中的元素，stx == 0则代表还没被a给拷贝过来，否则，stx记录的是从x点开始拷贝k个的那个x值，等会后面要用到。sty则是随stx，stx要更新时，sty也要更新，sty初始为0，这时的sty为拷贝从b的y个位置开始的那个y值，总之，即输入x,y,k，stx记录x，sty记录y。最后查询pos节点，如果其stx或sty为0，说明这个节点还没有受到“侵染“，保持原来的b数组中的值，所以输出b[pos]。否则，已经收到”侵染“，输出a[pos-sty+stx]，即从a中去与距离相等的元素，距离就是那个pos-sty，这时知道sty的作用了吧。。
代码：
/*3900KB 280ms*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100010 int a[N],b[N];
int n,m; struct node
{
int stx,sty;
}tree[*N]; void build(int l,int r,int rt)
{
tree[rt].stx = tree[rt].sty = ;
if(l == r)
{
return;
}
int mid = (l+r)/;
build(l,mid,*rt);
build(mid+,r,*rt+);
} void pushdown(int rt)
{
if(tree[rt].stx)
{
tree[*rt].stx = tree[*rt+].stx = tree[rt].stx;
tree[*rt].sty = tree[*rt+].sty = tree[rt].sty;
tree[rt].stx = tree[rt].sty = ;
}
}
void change(int l,int r,int aa,int bb,int stx,int sty,int rt)
{
if(aa<=l&&bb>=r)
{
tree[rt].stx = stx;
tree[rt].sty = sty;
return;
}
pushdown(rt);
int mid = (l+r)/;
if(bb<=mid)
change(l,mid,aa,bb,stx,sty,*rt);
else if(aa>mid)
change(mid+,r,aa,bb,stx,sty,*rt+);
else
{
change(l,mid,aa,bb,stx,sty,*rt);
change(mid+,r,aa,bb,stx,sty,*rt+);
}
} node query(int l,int r,int pos,int rt)
{
if(l == r)
{
return tree[rt];
}
pushdown(rt);
int mid = (l+r)/;
if(pos<=mid)
return query(l,mid,pos,*rt);
return query(mid+,r,pos,*rt+);
} int main()
{ int i;
int x,y,k,pos;
int op;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=;i<=n;i++)
{
scanf("%d",&b[i]);
}
build(,n,);
for(i=;i<m;i++)
{
scanf("%d",&op);
if(op == )
{
scanf("%d%d%d",&x,&y,&k);
change(,n,y,y+k-,x,y,);
}
else
{
scanf("%d",&pos);
node ans = query(,n,pos,);
if(ans.stx == )
{
printf("%d\n",b[pos]);
}
else
{
printf("%d\n",a[pos-ans.sty+ans.stx]);
}
}
}
}
return ;
}
E.Circular RMQ ---Codeforces 52C
也是很简单的一道线段树，纯当练手了，还是那样维护，只不过可能换成两个区间查询和加值罢了。。还有值得一提的输入方式，因为比较坑爹的是输入不定，所以借鉴了别人的stringstream 方法，核心代码如下：
gets(buffer);
stringstream ss(buffer);
ss>>aa>>bb;
具体实现在下面。。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <utility>
#include <cstdlib>
#include <sstream>
using namespace std;
#define N 200010 struct node
{
lll mini;
lll addmark;
}tree[*N]; int n,m;
lll a[N]; void pushup(int rt)
{
tree[rt].mini = min(tree[*rt].mini,tree[*rt+].mini);
} void build(int l,int r,int rt)
{
tree[rt].addmark = ;
if(l == r)
{
tree[rt].mini = a[l];
return;
}
int mid = (l+r)/;
build(l,mid,*rt);
build(mid+,r,*rt+);
pushup(rt);
} void pushdown(int rt)
{
if(tree[rt].addmark)
{
tree[*rt].mini += tree[rt].addmark;
tree[*rt+].mini += tree[rt].addmark;
tree[*rt].addmark += tree[rt].addmark;
tree[*rt+].addmark += tree[rt].addmark;
tree[rt].addmark = ;
}
} void add(int l,int r,int aa,int bb,int val,int rt)
{
if(aa>r||bb<l)
return;
if(aa<=l&&bb>=r)
{
tree[rt].mini += val;
tree[rt].addmark += val;
return;
}
pushdown(rt);
int mid = (l+r)/;
if(aa<=mid)
add(l,mid,aa,bb,val,*rt);
if(bb>mid)
add(mid+,r,aa,bb,val,*rt+);
pushup(rt);
} lll query(int l,int r,int aa,int bb,int rt)
{
if(aa>r||bb<l)
return (lll)1e17;
if(aa<=l&&bb>=r)
{
return tree[rt].mini;
}
pushdown(rt);
int mid = (l+r)/;
if(bb<=mid)
return query(l,mid,aa,bb,*rt);
else if(aa>mid)
return query(mid+,r,aa,bb,*rt+);
else
{
return min(query(l,mid,aa,bb,*rt),query(mid+,r,aa,bb,*rt+));
}
} char buffer[]; int main()
{
int i,aa,bb;
lll val,ans;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=n;i++)
{
scanf("%I64d",&a[i]);
}
build(,n,);
scanf("%d",&m);
gets(buffer);
for(i=;i<m;i++)
{
gets(buffer);
stringstream ss(buffer);
ss>>aa>>bb;
aa++,bb++;
if(ss>>val)
{
if(aa<=bb)
{
add(,n,aa,bb,val,);
}
else
{
add(,n,aa,n,val,);
add(,n,,bb,val,);
}
}
else
{
if(aa<=bb)
ans = query(,n,aa,bb,);
else
{
lll res = query(,n,aa,n,);
ans = query(,n,,bb,);
ans = min(ans,res);
}
printf("%I64d\n",ans);
}
}
}
return ;
}
H.Vessels ---Codeforces 371D
这道题我原来出的时候记得是线段树，但是后来看别人的代码，没看见一个用线段树写的，，我去。原来硬搞也能过。。难点是想到，。下面放我借鉴别人的代码吧：
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200010 int cap[N],jp[N],a[N]; int main()
{
int n,m;
int i,j;
int op,pos,val;
int st;
while(scanf("%d",&n)!=EOF)
{
memset(cap,,sizeof(cap));
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
jp[i] = i;
}
scanf("%d",&m);
for(i=;i<m;i++)
{
scanf("%d",&op);
if(op == )
{
scanf("%d%d",&pos,&val);
st = jp[pos];
while(cap[st]+val>=a[st]&&st<=n)
{
val -= (a[st]-cap[st]);
cap[st] = a[st];
st++;
}
if(st<=n)
cap[st] += val;
for(j=jp[pos];j<st;j++)
{
jp[j] = st;
}
jp[pos] = st;
}
else
{
scanf("%d",&pos);
printf("%d\n",cap[pos]);
}
}
}
return ;
}