Segment Tree with Lazy 分类: ACM TYPE 2014-08-29 11:28 134人阅读 评论(0) 收藏

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
int l, r, s;
}num[800005];
int n, m, key; void build(int l,int r,int k)
{
num[k].l = l;
num[k].r = r;
num[k].s = 0;
if(l == r)
{
num[k].s = 1;
return;
}
int mi = (l+r)>>1;
build(l,mi,k+k);
build(mi+1,r,k+k+1);
return;
} void update(int l, int r, int k)
{ if(num[k].s)
{
num[k+k].s = num[k+k+1].s = num[k].s;
num[k].s = 0;
}
if(num[k].l == l && num[k].r == r)
{
num[k].s = key;
return;
}
int mi = (num[k].l+num[k].r)>>1;
if(l > mi) update(l,r,k+k+1);
else if(r <= mi) update(l,r,k+k);
else
{
update(l,mi,k+k);
update(mi+1,r,k+k+1);
}
return;
} int query(int k)
{
if(num[k].s) return (num[k].r-num[k].l+1)*num[k].s;
else return query(k+k)+query(k+k+1);
} int main()
{
int Case;
int a, b;
scanf("%d",&Case);
for(int j=1;j<=Case;j++)
{
memset(num,0,sizeof(num));
scanf("%d",&n);
build(1,n,1);
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&a,&b,&key);
update(a,b,1);
}
printf("Case %d: The total value of the hook is %d.\n",j,query(1));
}
return 0;
}

Code From Hdu1698

版权声明:本文为博主原创文章,未经博主允许不得转载。

上一篇:Tomcat:基于HTTP协议的Connector配置


下一篇:二分图匹配(KM算法)n^4 分类: ACM TYPE 2014-10-04 11:36 88人阅读 评论(0) 收藏