題目的意思是給你一個數組，大小是N,初始的時候,a[1-N]均為1,然后有Q個操作，每次操作修改某個區(qū)間中的值，求最后整個區(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;
}發(fā)現我現場寫線段樹的能力太差，以后這種東西一定要能夠手寫，這題要好好總結一下。恩。東西學的多了，不一定是好事，對于靈活的東西一定要做到非常熟練，否則比賽的時候會很慢的。
#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;
}