【FOJ】1608 Huge Mission

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXN 50010
 6 struct time
 7 {
 8     int s,t,ef;
 9     friend bool operator<(time a,time b)
10     {
11         return a.ef>b.ef;
12     }
13 };
14 struct node
15 {
16     int sum,lazy;
17 };
18 time p[MAXN*10];
19 node tree[MAXN<<2];
20 void Build(int L,int R,int rt)
21 {
22     tree[rt].lazy=0;
23     tree[rt].sum=R-L+1;
24     if(L!=R)
25     {
26         int mid=(L+R)>>1;
27         Build(L,mid,rt<<1);
28         Build(mid+1,R,rt<<1|1);
29     }
30 }
31 inline void PushDown(int rt)
32 {
33     if(tree[rt].lazy)
34     {
35         tree[rt].lazy=0;
36         tree[rt<<1].lazy=tree[rt<<1|1].lazy=1;
37         tree[rt<<1].sum=tree[rt<<1|1].sum=0;
38     }
39 }
40 inline void PushUp(int rt)
41 {
42     tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
43 }
44 int Query(int x,int y,int L,int R,int rt)
45 {
46     if(x<=L&&R<=y)
47         return tree[rt].sum;
48     int ans=0,mid=(L+R)>>1;
49     PushDown(rt);
50     if(x<=mid)
51         ans+=Query(x,y,L,mid,rt<<1);
52     if(y>mid)
53         ans+=Query(x,y,mid+1,R,rt<<1|1);
54     return ans;
55 }
56 void Update(int x,int y,int L,int R,int rt)
57 {
58     if(x<=L&&R<=y)
59     {
60         tree[rt].lazy=1;
61         tree[rt].sum=0;
62     }
63     else
64     {
65         int mid=(L+R)>>1;
66         PushDown(rt);
67         if(x<=mid)
68             Update(x,y,L,mid,rt<<1);
69         if(y>mid)
70             Update(x,y,mid+1,R,rt<<1|1);
71         PushUp(rt);
72     }
73 }
74 int main()
75 {
76     int i,n,m,ans;
77     while(~scanf("%d%d",&n,&m))
78     {
79         Build(0,n-1,1);
80         for(i=0;i<m;i++)
81             scanf("%d%d%d",&p[i].s,&p[i].t,&p[i].ef);
82         sort(p,p+m);
83         for(i=ans=0;i<m;i++)
84         {
85             ans+=p[i].ef*Query(p[i].s,p[i].t-1,0,n-1,1);
86             Update(p[i].s,p[i].t-1,0,n-1,1);
87         }
88         printf("%d\n",ans);
89     }
90     return 0;
91 }
新博客：www.zhixiangli.com