最大矩阵覆盖权值--(静态连续最大子段 (线段树) )-HDU(6638)Snowy Smile

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>
  6 #include <bitset>
  7 #include <map>
  8 //#include<unordered_map>    http://acm.hdu.edu.cn/showproblem.php?pid=6638
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(arr,arr+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(arr+1,arr+1+n);//prev_permutation
 23 #define fo(arr,b,c) for(register int arr=b;arr<=c;++arr)
 24 #define fr(arr,b,c) for(register int arr=b;arr>=c;--arr)
 25 #define mem(arr,b) memset(arr,b,sizeof(arr))
 26 #define pr printf
 27 #define sc scanf
 28 #define ls rt<<1
 29 #define rs rt<<1|1
 30 void swapp(int &arr,int &b);
 31 double fabss(double arr);
 32 int maxx(int arr,int b);
 33 int minn(int arr,int b);
 34 int Del_bit_1(int n);
 35 int lowbit(int n);
 36 int abss(int arr);
 37 //const long long INF=(1LL<<60);
 38 const double E=2.718281828;
 39 const double PI=acos(-1.0);
 40 const int inf=(1<<29);
 41 const double ESP=1e-9;
 42 const int mod=(int)1e9+7;
 43 const int N=(int)2003;
 44 
 45 int b[N];
 46 struct node_
 47 {
 48     int x,y;
 49     long long v;
 50     friend bool operator<(node_ a,node_ b)
 51     {
 52         if(a.y==b.y)
 53             return a.x<b.x;
 54         return a.y>b.y;
 55     }
 56 }arr[N];
 57 struct vnode
 58 {
 59     int x;
 60     long long v;
 61 };
 62 //=================================================离散化;
 63 int LSx(int n)
 64 {
 65     int m=0;
 66     for(int i=1;i<=n;++i)
 67         b[++m]=arr[i].x;
 68     sort(b+1,b+1+m);
 69     m=unique(b+1,b+1+m)-b-1;
 70     for(int i=1;i<=n;++i)
 71         arr[i].x=lower_bound(b+1,b+1+m,arr[i].x)-b;
 72     return m;
 73 }
 74 int LSy(int n)
 75 {
 76     int m=0;
 77     for(int i=1;i<=n;++i)
 78         b[++m]=arr[i].y;
 79     sort(b+1,b+1+m);
 80     m=unique(b+1,b+1+m)-b-1;
 81     for(int i=1;i<=n;++i)
 82         arr[i].y=lower_bound(b+1,b+1+m,arr[i].y)-b;
 83     return m;
 84 }
 85 //===========================================连续子段线段树;
 86 struct node
 87 {
 88     long long Sum,Lsum,Rsum,ans;
 89 }tr[N<<2];
 90 
 91 void up(int rt)
 92 {
 93     tr[rt].Sum=tr[ls].Sum+tr[rs].Sum;
 94     tr[rt].ans=max(max(tr[ls].ans,tr[rs].ans),tr[ls].Rsum+tr[rs].Lsum);
 95     tr[rt].Lsum=max(tr[ls].Lsum,tr[ls].Sum+tr[rs].Lsum);
 96     tr[rt].Rsum=max(tr[rs].Rsum,tr[rs].Sum+tr[ls].Rsum);
 97 }
 98 void Build(int l,int r,int rt)
 99 {
100     if(l==r)
101     {
102         tr[rt].Sum=tr[rt].Lsum=tr[rt].Rsum=tr[rt].ans=0;
103         return;
104     }
105     int mid=(l+r)>>1;
106     Build(l,mid,ls);
107     Build(mid+1,r,rs);
108     up(rt);
109 }
110 void update_dot(int pos,long long v,int l,int r,int rt)
111 {
112     if(l==r)
113     {
114         tr[rt].Sum+=v;
115         tr[rt].Lsum=tr[rt].Rsum=tr[rt].ans=tr[rt].Sum;
116         return;
117     }
118     int mid=(l+r)>>1;
119     if(pos<=mid)
120         update_dot(pos,v,l,mid,ls);
121     else
122         update_dot(pos,v,mid+1,r,rs);
123     up(rt);
124 }
125 vector<vector<vnode> >v(N);
126 
127 int main()
128 {
129     int T;
130     sc("%d",&T);
131     while(T--)
132     {
133         int n;
134         sc("%d",&n);
135         for(int i=1;i<=n;++i)
136             sc("%d%d%lld",&arr[i].x,&arr[i].y,&arr[i].v);
137         int L=LSx(n);
138         int H=LSy(n);
139         fo(i,1,H)v[i].clear();
140         for(int i=1;i<=n;++i)
141             v[arr[i].y].push_back({arr[i].x,arr[i].v});
142         long long ans=0;
143         for(int i=H;i>=1;--i)
144         {
145             Build(1,L,1);
146             for(int j=i;j>=1;--j)
147             {
148                 int sz=v[j].size();
149                 for(int k=0;k<sz;++k)
150                 {
151                     vnode t=v[j][k];
152                     update_dot(t.x,t.v,1,L,1);
153                 }
154                 ans=max(ans,tr[1].ans);//每增加一层就更新答案;
155             }
156         }
157         pr("%lld\n",ans);
158     }
159     return 0;
160 }
161 
162 /**************************************************************************************/
163 
164 int maxx(int arr,int b)
165 {
166     return arr>b?arr:b;
167 }
168 
169 void swapp(int &arr,int &b)
170 {
171     arr^=b^=arr^=b;
172 }
173 
174 int lowbit(int n)
175 {
176     return n&(-n);
177 }
178 
179 int Del_bit_1(int n)
180 {
181     return n&(n-1);
182 }
183 
184 int abss(int arr)
185 {
186     return arr>0?arr:-arr;
187 }
188 
189 double fabss(double arr)
190 {
191     return arr>0?arr:-arr;
192 }
193 
194 int minn(int arr,int b)
195 {
196     return arr<b?arr:b;
197 }