计蒜客 28315.Excellent Engineers-线段树(单点更新、区间最值) (Benelux Algorithm Programming Contest 2014 Final ACM-ICPC Asia Training League 暑假第一阶段第二场 E)

 1 //E-线段树
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<cstdlib>
 8 #include<queue>
 9 #include<stack>
10 using namespace std;
11 typedef long long ll;
12 const int inf=0x3f3f3f3f;
13 const double eps=1e-5;
14 const int maxn=1e5+10;
15 #define lson l,m,rt<<1
16 #define rson m+1,r,rt<<1|1
17 struct node
18 {
19     int x,y,z;
20     bool operator<(const node&a)const
21     {
22         return x<a.x;
23     }
24 }a[maxn];
25 int tree[maxn<<2];
26 
27 void PushUp(int rt)
28 {
29     tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
30 }
31 
32 void build(int l,int r,int rt)
33 {
34     if(l==r)
35     {
36         tree[rt]=inf;
37         return ;
38     }
39     int m=(l+r)>>1;
40     build(lson);
41     build(rson);
42     PushUp(rt);
43 }
44 //单点更新
45 void update(int pos,int val,int l,int r,int rt)
46 {
47     if(l==r)
48     {
49         tree[rt]=val;
50         return ;
51     }
52     int m=(l+r)>>1;
53     if(pos<=m)update(pos,val,lson);
54     else update(pos,val,rson);
55     PushUp(rt);
56 }
57 
58 //区间最值
59 int query(int L,int R,int l,int r,int rt)
60 {
61     if(L<=l&&r<=R)
62     {
63         return tree[rt];
64     }
65     int m=(l+r)>>1;
66     int ret=inf;
67     if(L<=m)ret=min(ret,query(L,R,lson));
68     if(R> m)ret=min(ret,query(L,R,rson));
69     return ret;
70 }
71 
72 
73 int main()
74 {
75     int t,n;
76     scanf("%d",&t);
77     while(t--)
78     {
79         scanf("%d",&n);
80         build(1,n,1);
81         for(int i=0;i<n;i++)
82             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
83         sort(a,a+n);
84         int ans=0;
85         for(int i=0;i<n;i++)
86         {
87             if(a[i].y!=1)
88             {
89                 int cnt=query(1,a[i].y-1,1,n,1);
90                 if(cnt<a[i].z)continue;
91             }
92             ans++;
93             update(a[i].y,a[i].z,1,n,1);
94         }
95         printf("%d
",ans);
96     }
97     return 0;
98 }