hdu（1698）Just a Hook

本文主要是介绍hdu（1698）Just a Hook，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出一个数列，初始值都是1，进行一种操作：给出一个区间，将该区间内的数值全部换为2或3或不变，求数列最后的总和。

#include"stdio.h"
#include"string.h"
struct  point
{
int x,y;
int sum,add;
}a[400100];
void tree(int t,int x,int y)
{
a[t].x=x;
a[t].y=y;
a[t].add=0;
if(x==y)
{
a[t].sum=1;
return ;
}
int temp=2*t;
int mid=(x+y)/2;
tree(temp,x,mid);
tree(temp+1,mid+1,y);
a[t].sum=a[temp].sum+a[temp+1].sum;
}
void find(int t,int x,int y,int val)
{
if(a[t].x>y||a[t].y<x)
return ;
if(x<=a[t].x&&y>=a[t].y)
{
a[t].sum=(a[t].y-a[t].x+1)*val;
a[t].add=val;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(a[t].add)
{
a[temp].add=a[temp+1].add=a[t].add;
a[temp].sum=(a[temp].y-a[temp].x+1)*a[temp].add;
a[temp+1].sum=(a[temp+1].y-a[temp+1].x+1)*a[temp+1].add;
a[t].add=0;
}
find(temp,x,y,val);
find(temp+1,x,y,val);
a[t].sum=a[temp].sum+a[temp+1].sum;
}
int main()
{
int n,m,k,r=1;
scanf("%d",&k);
while(k--)
{
scanf("%d",&m);
tree(1,1,m);
scanf("%d",&n);
while(n--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
find(1,a,b,c);
}
printf("Case %d: The total value of the hook is %d.\n",r++,a[1].sum);
}
return 0;
}

 

 

#include"stdio.h"
#include"string.h"
struct  point
{
 int x,y;
 int sum,add;
}a[400100];
void tree(int t,int x,int y)
{
 a[t].x=x;
 a[t].y=y;
 a[t].add=0;
 if(x==y)
 {
  a[t].sum=1;
  return ;
 }
 int temp=2*t;
 int mid=(x+y)/2;
 tree(temp,x,mid);
 tree(temp+1,mid+1,y);
 a[t].sum=a[temp].sum+a[temp+1].sum;
}
void find(int t,int x,int y,int val)
{
 if(x==a[t].x&&y==a[t].y)
 {
  a[t].sum=(a[t].y-a[t].x+1)*val;
  a[t].add=val;
  return ;
 }
 int temp=2*t;
 int mid=(a[t].x+a[t].y)/2;
 if(a[t].add)
 {
  a[temp].add=a[temp+1].add=a[t].add;
  a[temp].sum=(a[temp].y-a[temp].x+1)*a[temp].add;
  a[temp+1].sum=(a[temp+1].y-a[temp+1].x+1)*a[temp+1].add;
  a[t].add=0;
 }
 if(y<=mid)
  find(temp,x,y,val);
 else if(x>mid)
  find(temp+1,x,y,val);
 else
 {
  find(temp,x,mid,val);
  find(temp+1,mid+1,y,val);
 }
 a[t].sum=a[temp].sum+a[temp+1].sum;
}
int main()
{
 int n,m,k,r=1;
 scanf("%d",&k);
 while(k--)
 {
  scanf("%d",&m);
  tree(1,1,m);
  scanf("%d",&n);
  while(n--)
  {
   int a,b,c;
   scanf("%d%d%d",&a,&b,&c);
   find(1,a,b,c);
  }
  printf("Case %d: The total value of the hook is %d.\n",r++,a[1].sum);
 }
 return 0;
}

 

 

 

和poj3468的方法一样，只不过这个sum，add等不需要累加，即可；

 

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int ans;
struct point
{
int x,y;
int sum,add;
}a[400100];
void tree(int t,int x,int y)
{
a[t].x=x;a[t].y=y;
a[t].add=0;
if(x==y)
{
a[t].sum=1;
return ;
}
int temp=2*t;
int mid=(x+y)/2;
tree(temp,x,mid);
tree(temp+1,mid+1,y);
a[t].sum=a[temp].sum+a[temp+1].sum;
}
void updata(int t,int x,int y,int val)
{
if(a[t].x>y||a[t].y<x)
return ;
if(a[t].x>=x&&a[t].y<=y)
{
a[t].sum=val*(a[t].y-a[t].x+1);
a[t].add=val;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(a[t].add)
{
a[temp].sum=(a[temp].y-a[temp].x+1)*a[t].add;
a[temp+1].sum=(a[temp+1].y-a[temp+1].x+1)*a[t].add;
a[temp].add=a[t].add;
a[temp+1].add=a[t].add;
a[t].add=0;
}
updata(temp,x,y,val);
updata(temp+1,x,y,val);
a[t].sum=a[temp+1].sum+a[temp].sum;
}
void find(int t,int x,int y)
{
if(a[t].x>y||a[t].y<x)
return ;
if(a[t].x>=x&&a[t].y<=y)
{
ans+=a[t].sum;
return ;
}
int temp=2*t;
int mid=(a[t].x+a[t].y)/2;
if(a[t].add)
{
a[temp].sum=(a[temp].y-a[temp].x+1)*a[t].add;
a[temp+1].sum=(a[temp+1].y-a[temp+1].x+1)*a[t].add;
a[temp].add=a[t].add;
a[temp+1].add=a[t].add;
a[t].add=0;
}
find(temp,x,y);
find(temp+1,x,y);
a[t].sum=a[temp+1].sum+a[temp].sum;
}
int main()
{
int m,n,k,a,b,c,r=1;
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&n,&m);
tree(1,1,n);
ans=0;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
updata(1,a,b,c);
}
find(1,1,n);
printf("Case %d: The total value of the hook is %d.\n",r++,ans);
}
return 0;
}

 

 

这篇关于hdu（1698）Just a Hook的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---