http://acm.hdu.edu.cn/showproblem.php?pid=1698
这个题意翻译起来有点猥琐啊,还是和谐一点吧
和涂颜色差不多,区间初始都为1,然后操作都是将x到y改为z,注意 是改为z,不是加或减,最后输出区间总值
也是线段树加lazy操作
#include<cstdio>
using namespace std;
struct point {
int l,r;
int val,sum;
};
point tree[];
void build(int i,int left,int right)
{
tree[i].l=left,tree[i].r=right;
tree[i].val=;
if (left==right) {tree[i].sum=;return;}
int mid=(left+right)/;
build(i*,left,mid);
build(i*+,mid+,right);
tree[i].sum=tree[i*].sum+tree[i*+].sum;
}
int update(int i,int left,int right,int val)
{
if (right==tree[i].r&&left==tree[i].l)
{
tree[i].val=val;
return tree[i].sum=(right-left+)*val;
}
if (tree[i].val)
{
tree[i*].val=tree[i*+].val=tree[i].val;
tree[i*].sum=(tree[i*].r-tree[i*].l+)*tree[i].val;
tree[i*+].sum=(tree[i*+].r-tree[i*+].l+)*tree[i].val;
tree[i].val=;
}
int mid=(tree[i].r+tree[i].l)/;
if (left>mid) return tree[i].sum=update(i*+,left,right,val)+tree[i*].sum;
else if (right<=mid) return tree[i].sum=update(i*,left,right,val)+tree[i*+].sum;
else return tree[i].sum=update(i*+,mid+,right,val)+update(i*,left,mid,val);
}
int main()
{
int t,n,m,x,y,z,sum;
while (~scanf("%d",&t))
{
sum=;
while (t--)
{
scanf("%d %d",&n,&m);
build(,,n);
while (m--)
{
scanf("%d %d %d",&x,&y,&z);
update(,x,y,z);
}
printf("Case %d: The total value of the hook is %d.\n",sum++,tree[].sum);
}
}
return ;
}
http://poj.org/problem?id=3468
这个和上面一样,只是变成了加上z,所以就变成了在原有的值上再加,+=，改改就行,数值比较大,应该用int64
#include<cstdio>
#define ll __int64
using namespace std;
struct point {
ll l,r;
ll val,sum;
};
point tree[];
ll num[];
void build(ll i,ll left,ll right)
{
tree[i].l=left,tree[i].r=right;
tree[i].val=;
if (left==right) {tree[i].sum=num[left];return;}
int mid=(left+right)/;
build(i*,left,mid);
build(i*+,mid+,right);
tree[i].sum=tree[i*].sum+tree[i*+].sum;
}
ll update(ll i,ll left,ll right,ll val)
{
if (right==tree[i].r&&left==tree[i].l)
{
tree[i].val+=val;
return tree[i].sum+=(right-left+)*val;
}
if (tree[i].val)
{
tree[i*].val+=tree[i].val;
tree[i*+].val+=tree[i].val;
tree[i*].sum+=(tree[i*].r-tree[i*].l+)*tree[i].val;
tree[i*+].sum+=(tree[i*+].r-tree[i*+].l+)*tree[i].val;
tree[i].val=;
}
int mid=(tree[i].r+tree[i].l)/;
if (left>mid) return tree[i].sum=update(i*+,left,right,val)+tree[i*].sum;
else if (right<=mid) return tree[i].sum=update(i*,left,right,val)+tree[i*+].sum;
else return tree[i].sum=update(i*+,mid+,right,val)+update(i*,left,mid,val);
}
ll find(ll i,ll left,ll right)
{
if (left>tree[i].r&&right<tree[i].l) return ;
if (tree[i].l==left&&tree[i].r==right) return tree[i].sum;
if (tree[i].val)
{
tree[i*].val+=tree[i].val;
tree[i*+].val+=tree[i].val;
tree[i*].sum+=(tree[i*].r-tree[i*].l+)*tree[i].val;
tree[i*+].sum+=(tree[i*+].r-tree[i*+].l+)*tree[i].val;
tree[i].val=;
}
ll mid=(tree[i].r+tree[i].l)/;
if (left>mid) return find(i*+,left,right);
else if (right<=mid) return find(i*,left,right);
else return find(i*,left,mid)+find(i*+,mid+,right);
}
int main()
{
ll n,m,i,z,x,y;
char op;
while (~scanf("%I64d %I64d",&n,&m))
{
for (i=;i<=n;i++)
scanf("%I64d",&num[i]);
build(,,n);
while (m--)
{
scanf(" %c",&op);
if (op=='C')
{
scanf("%I64d %I64d %I64d",&x,&y,&z);
update(,x,y,z);
}
else
{
scanf("%I64d %I64d",&x,&y);
printf("%I64d\n",find(,x,y));
}
}
}
return ;
}