hdu 1698 just the hook
发布时间
阅读量：
阅读量
http://acm.hdu.edu.cn/showproblem.php?pid=1698
如果更新到叶子节点会超时的
#include<iostream>
using namespace std;
const int N=100001,NN=3*N;
struct segtree
{
int left,right,num;
int mid()
{
return (left+right)/2;
}
}st[NN];
void build(int left,int right,int id)
{
st[id].left=left;
st[id].right=right;
st[id].num=1;
if(left==right)
return ;
int mid=st[id].mid();
build(left,mid,id*2);
build(mid+1,right,id*2+1);
}
void update(int left,int right,int x,int id)
{
if(left<=st[id].left&&right>=st[id].right)
{
st[id].num=x;
return ;
}
if(st[id].num!=-1)
{
st[id*2].num=st[id*2+1].num=st[id].num;
st[id].num=-1;
}
int mid=st[id].mid();
if(right<=mid)
update(left,right,x,id*2);
else if(left>mid)
update(left,right,x,id*2+1);
else
{
update(left,mid,x,id*2);
update(mid+1,right,x,id*2+1);
}
}
int query(int left,int right,int id)
{
int mid;
if(st[id].left==left&&st[id].right==right)
{
if(st[id].num!=-1)
return (right-left+1)*st[id].num;
else
{
mid=st[id].mid();
return query(left,mid,id*2)+query(mid+1,right,id*2+1);
}
}
mid=st[id].mid();
if(right<=mid)
return query(left,right,id*2);
else if(left>mid)
return query(left,right,id*2+1);
else
return query(left,mid,id*2)+query(mid+1,right,id*2+1);
}
int main()
{
int t,m,n,ca=0,a,b,c;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
build(1,m,1);
while(n--)
{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1);
}
printf("Case %d: The total value of the hook is %d.\n",++ca,query(1,m,1));
}
return 0;
}
代码解读全部评论 (0)
还没有任何评论哟~