2014年山东省第五届ACM大学生程序设计竞赛Devour Magic（线段树）

线段树）"/>

2014年山东省第五届ACM大学生程序设计竞赛Devour Magic（线段树）

简简单单的写个线段树，查询都不需要。还int超时了一下。。。

每次把l，r的值更新为当前输入的t就行了。

#include <bits/stdc++.h>
using namespace std;
long long tree[400009];
long long lazy[400009];
void pushback(long long root,long long l,long long r)
{if(lazy[root]){long long mid=(r+l)/2;tree[root<<1]=(mid-l+1)*lazy[root];lazy[root<<1]=lazy[root];tree[root<<1|1]=(r-mid)*lazy[root];lazy[root<<1|1]=lazy[root];lazy[root]=0;}
}
void update(long long l,long long r,long long L,long long R,long long val,long long root)
{if(L>R)return;if(L==R){tree[root]=val;return ;}pushback(root,L,R);if(l<=L&&r>=R){tree[root]=val*(R-L+1);lazy[root]=val;return;}long long mid=(L+R)/2;if(mid>=r)update(l,r,L,mid,val,root<<1);else if(mid<l)update(l,r,mid+1,R,val,root<<1|1);else{update(l,r,L,mid,val,root<<1);update(l,r,mid+1,R,val,root<<1|1);}tree[root]=tree[root<<1]+tree[root<<1|1];
}
int main()
{long long t,n,m;scanf("%lld",&t);while(t--){memset(tree,0,sizeof(tree));memset(lazy,0,sizeof(lazy));long long now,l,r;scanf("%lld%lld",&n,&m);while(m--){scanf("%lld%lld%lld",&now,&l,&r);update(l,r,1,n,now,1);}long long ans=0;ans=tree[1];printf("%lld\n",ans);}return 0;
}