POJ3277 线段树段更新，点询问+二分离散化+暴力

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

      首先范围很大，n很小，果断离散化，然后我们就是求出任意区间的最大值作为当前区间的高，最后在算一遍答案就行了，一开始超时了，离散化的时候用map了，后来改成二分就ac了，感觉题目不是很难，明天得开始学习学习扫描线了，还不知道什么是扫描线呢。

#include<stdio.h>
#include<string.h>
#include<algorithm>#define lson l ,mid ,t << 1
#define rson mid + 1 ,r ,t << 1 | 1using namespace std;typedef struct
{__int64 a ,b ,c;
}EDGE;EDGE edge[44000];__int64 Max[330000];
__int64 mark[330000];
__int64 tmp[88000];
__int64 num[88000];
__int64 hash[880000];__int64 maxx(__int64 x ,__int64 y)
{return x > y ? x : y;
}void Pushup(__int64 t)
{Max[t] = maxx(Max[t<<1] ,Max[t<<1|1]);
}void Pushdown(__int64 t)
{if(mark[t]){mark[t<<1] = maxx(mark[t<<1] ,mark[t]);mark[t<<1|1] = maxx(mark[t<<1|1] ,mark[t]);Max[t<<1] = maxx(Max[t<<1] ,mark[t]);Max[t<<1|1] = maxx(Max[t<<1|1] ,mark[t]);mark[t] = 0;}
}void BuidTree()
{memset(Max ,0 ,sizeof(Max));memset(mark ,0 ,sizeof(mark));
}void Update(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b ,__int64 c)
{if(a <= l && b >= r){Max[t] = maxx(Max[t] ,c);mark[t] = maxx(mark[t] ,c);return;}Pushdown(t);__int64 mid = (l + r) >> 1;if(a <= mid) Update(lson ,a ,b ,c);if(b > mid)  Update(rson ,a ,b ,c);Pushup(t);
}__int64 Query(__int64 l ,__int64 r ,__int64 t ,__int64 a)
{if(l == r) return Max[t];Pushdown(t);__int64 mid = (l + r) >> 1;if(a <= mid) return Query(lson ,a);else return Query(rson ,a);
} __int64 search2(__int64 n ,__int64 now)
{__int64 low ,up ,mid ,ans;low = 1 ,up = n;while(low <= up){mid = (low + up) >> 1;if(now <= num[mid]){ans = mid;up = mid - 1;}else low = mid + 1;}return ans;
}int main ()
{__int64 n ,i;while(~scanf("%I64d" ,&n)){__int64 id = 0;for(i = 1 ;i <= n ;i ++){scanf("%I64d %I64d %I64d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);tmp[++id] = edge[i].a;tmp[++id] = edge[i].b;}sort(tmp + 1 ,tmp + id + 1);tmp[0] = -1;for(id = 0 ,i = 1 ;i <= n * 2 ;i ++){if(tmp[i] == tmp[i-1]) continue;num[++id] = tmp[i];}       BuidTree();for(i = 1 ;i <= n ;i ++){__int64 a = search2(id ,edge[i].a);__int64 b = search2(id ,edge[i].b);    Update(1 ,id ,1 ,a + 1 ,b ,edge[i].c);}__int64 ans = 0;for(i = 2 ;i <= id ;i ++){__int64 now = Query(1 ,id ,1 ,i);now = (num[i] - num[i-1]) * now;ans += now;}printf("%I64d
" ,ans);}return 0;
}