- hdu1698
- http://acm.hdu.edu.cn/showproblem.php?pid=1698
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- #include <time.h>
- #include <string>
- #include <set>
- #include <map>
- #include <list>
- #include <stack>
- #include <queue>
- #include <vector>
- #include <bitset>
- #include <ext/rope>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- #define ll long long
- #define minv 1e-6
- #define inf 1e9
- #define pi 3.1415926536
- #define E 2.7182818284
- const ll mod=1e9+7;//998244353
- const int maxn=1e5+10;
- int tag[maxn<<2],sum[maxn<<2];
- void push_down(int index,int len)
- {
- tag[index<<1]=tag[index<<1|1]=tag[index];
- sum[index<<1]=((len+1)>>1)*tag[index];
- sum[index<<1|1]=(len>>1)*tag[index];
- tag[index]=0;
- }
- void build(int index,int l,int r)
- {
- tag[index]=0;
- if (l==r)
- sum[index]=1;
- else
- {
- int m=(l+r)>>1;
- build(index<<1,l,m);
- build(index<<1|1,m+1,r);
- sum[index]=sum[index<<1]+sum[index<<1|1];
- }
- }
- void update(int index,int l,int r,int s,int t,int v)
- {
- if (s<=l && r<=t)
- {
- tag[index]=v;
- sum[index]=(r-l+1)*v;
- return;
- }
- if (tag[index]!=0)
- push_down(index,r-l+1);
- int m=(l+r)>>1;
- if (s<=m)
- update(index<<1,l,m,s,t,v);
- if (m<t)
- update(index<<1|1,m+1,r,s,t,v);
- sum[index]=sum[index<<1]+sum[index<<1|1];
- }
- int query(int index,int l,int r,int s,int t)
- {
- if (s<=l && r<=t)
- return sum[index];
- if (tag[index]!=0)
- push_down(index,r-l+1);
- if (r<s || l>t)
- return 0;
- else
- {
- int m=(l+r)>>1;
- return query(index<<1,l,m,s,t)+query(index<<1|1,m+1,r,s,t);
- }
- }
- int main()
- {
- int t,T,n,q,x,y,v;
- scanf("%d",&t);
- for (T=1;T<=t;T++)
- {
- scanf("%d",&n);
- build(1,1,n);
- scanf("%d",&q);
- while (q--)
- {
- scanf("%d%d%d",&x,&y,&v);
- update(1,1,n,x,y,v);
- }
- printf("Case %d: The total value of the hook is %d.\n",T,query(1,1,n,1,n));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2737218.html