题目的意思是给你一个数组，大小是N,初始的时候,a[1-N]均为1,然后有Q个操作，每次操作修改某个区间中的值，求最后整个区间1-N的和。线段树解决
#include<iostream>
using namespace std;
int const maxn=100100;
struct node
{
int n;
int l,r;
}tree[maxn*4];
void build(int l,int r,int i)
{
tree[i].l=l;
tree[i].r=r;
if(l==r)
return;
int mid=(l+r)>>1;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
}
void update(int l,int r,int n,int i)
{
if(l==tree[i].l&&r==tree[i].r)
{
tree[i].n=n;
return ;
}
if(l>r)
return ;
int nn=tree[i].n;
if(tree[i].n!=0)
{
if(l!=tree[i].l||r!=tree[i].r)
{
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
{
update(l,r,n,i*2);
update(tree[i].l,l-1,nn,i*2);
update(r+1,mid,nn,i*2);
update(mid+1,tree[i].r,nn,i*2+1);
}
else if(l>mid)
{
update(l,r,n,i*2+1);
update(r+1,tree[i].r,nn,i*2+1);
update(mid+1,l-1,nn,i*2+1);
update(tree[i].l,mid,nn,i*2);
}
else
{
update(l,mid,n,i*2);
update(mid+1,r,n,i*2+1);
update(tree[i].l,l-1,nn,i*2);
update(r+1,tree[i].r,nn,i*2+1);
}
}
tree[i].n=0;
}
else if(tree[i].n==0)
{
if(l!=tree[i].l||r!=tree[i].r)
{
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
update(l,r,n,i*2);
else if(l>mid)
update(l,r,n,i*2+1);
else
{
update(l,mid,n,i*2);
update(mid+1,r,n,i*2+1);
}
}
}
}
int Que(int l,int r,int i)
{
int ans=0;
if(tree[i].l==l&&tree[i].r==r&&tree[i].n!=0)
{
ans=(r-l+1)*tree[i].n;
return ans;
}
else
{
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
ans= Que(l,r,i*2);
else if(l>mid)
ans= Que(l,r,i*2+1);
else
ans=Que(l,mid,i*2)+Que(mid+1,r,i*2+1);
return ans;
}
}
int main()
{
int ca;
scanf("%d",&ca);
int t=0;
while(ca--)
{
t++;
int n;
scanf("%d",&n);
build(1,n,1);
tree[1].n=1;
int q;
scanf("%d",&q);
int i;
for(i=1;i<=q;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1);
}
printf("Case %d: The total value of the hook is %d.\n",t,Que(1,n,1));
}
return 0;
}发现我现场写线段树的能力太差，以后这种东西一定要能够手写，这题要好好总结一下。恩。东西学的多了，不一定是好事，对于灵活的东西一定要做到非常熟练，否则比赛的时候会很慢的。
#include<iostream>
using namespace std;
int const maxn=100100;
struct node
{
int n;
int l,r;
}tree[maxn*4];
void build(int l,int r,int i)
{
tree[i].l=l;
tree[i].r=r;
tree[i].n=1;
if(l==r)
return;
int mid=(l+r)>>1;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
}
void update(int l,int r,int n,int i)
{
int nn=tree[i].n;
if(l==tree[i].l&&r==tree[i].r)
{
tree[i].n=n;
return ;
}
if(tree[i].n!=0)
{
tree[i*2].n=tree[i].n;
tree[i*2+1].n=tree[i].n;
tree[i].n=0;
}
int mid=(tree[i].l+tree[i].r)>>1;
{
if(r<=mid)
update(l,r,n,i*2);
else if(l>mid)
update(l,r,n,i*2+1);
else
{
update(l,mid,n,i*2);
update(mid+1,r,n,i*2+1);
}
}
}
int Que(int l,int r,int i)
{
int ans=0;
if(tree[i].l==l&&tree[i].r==r&&tree[i].n!=0)
{
ans=(r-l+1)*tree[i].n;
return ans;
}
else
{
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
ans= Que(l,r,i*2);
else if(l>mid)
ans= Que(l,r,i*2+1);
else
ans=Que(l,mid,i*2)+Que(mid+1,r,i*2+1);
return ans;
}
}
int main()
{
int ca;
scanf("%d",&ca);
int t=0;
while(ca--)
{
t++;
int n;
scanf("%d",&n);
build(1,n,1);
tree[1].n=1;
int q;
scanf("%d",&q);
int i;
for(i=1;i<=q;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1);
}
printf("Case %d: The total value of the hook is %d.\n",t,Que(1,n,1));
}
return 0;
}