此題AC了不止一次，用線段樹和樹狀數(shù)組都實現(xiàn)過。
以下是我的代碼：
#include<cstdio>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)^1)
using namespace std;
const int kMaxn(100007);
struct Node
{
int a,b,kind,sum;
};
int N,Q;
Node tree[kMaxn<<2];
void Build(int node,int x,int y)
{
tree[node].a=x;
tree[node].b=y;
tree[node].kind=0;
if(x==y)
tree[node].sum=1;
else
{
int m((x+y)>>1);
Build(L(node),x,m);
Build(R(node),m+1,y);
tree[node].sum=tree[L(node)].sum+tree[R(node)].sum;
}
}
void Modify(int node,int x,int y,int z)
{
if(x<=tree[node].a && tree[node].b<=y)
{
tree[node].kind=z;
tree[node].sum=(tree[node].b-tree[node].a+1)*z;
}
else
{
if(tree[node].kind)
{
tree[L(node)].kind=tree[R(node)].kind=tree[node].kind;
tree[node].kind=0;
tree[L(node)].sum=(tree[L(node)].b-tree[L(node)].a+1)*tree[L(node)].kind;
tree[R(node)].sum=(tree[R(node)].b-tree[R(node)].a+1)*tree[R(node)].kind;
}
int m((tree[node].a+tree[node].b)>>1);
if(x<=m)
Modify(L(node),x,y,z);
if(m+1<=y)
Modify(R(node),x,y,z);
tree[node].sum=tree[L(node)].sum+tree[R(node)].sum;
}
}
int main()
{
int T;
scanf("%d",&T);
for(int case_num=1;case_num<=T;case_num++)
{
scanf("%d%d",&N,&Q);
Build(1,1,N);
while(Q--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
Modify(1,x,y,z);
}
printf("Case %d: The total value of the hook is %d.\n",case_num,tree[1].sum);
}
return 0;
}
posted on 2011-07-31 09:24
lee1r 閱讀(346)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結構