首页 > 代码库 > HDU 4831
HDU 4831
这是百度之星初赛的题目。当时我是报名了百度之星的，但是因为要出去比赛，所以就错过了预赛，之后也一直没有关注。
但是昨天，我无意之间看见了百度之星，就想试一下。可是这一做不要紧，忽然发现自己什么都不会了。
4道题一道也做不出来。于是今天我决定好好做一下。
这道题是一道典型的线段树的题。题目就是说，有一些景点和休息区，景点有一个热度，休息区的热度等于最近的景点的热度，距离一样就取最大值。
接着是更新，U a b， 下标为a的景点热度更新为b， Q a 所有的景点和休息区中，热度小于等于a的有多少个。
我想的就是线段树中存区间的最大值和最小值以及热度和他相同的休息区的个数，查询很方便。更新的话，就要考虑休息区的热度如何选择了。
下面是代码
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int maxn = 10010;struct N{ int l, r; int max, min; int sign, front, back;} tr[maxn * 4];int h[maxn], dis[maxn], near[maxn], pos[maxn], change[maxn];int front[maxn], back[maxn];void init(){ memset(front, 0, sizeof(front)); memset(back, 0, sizeof(back)); memset(near, 0, sizeof(near)); h[0] = 0;}void build(int l, int r, int root){ tr[root].l = l; tr[root].r = r; if(l == r) { tr[root].min = h[l]; tr[root].max = h[l]; tr[root].back = back[l]; tr[root].front = front[l]; tr[root].sign = near[l] + 1; dis[l] = root; return ; } int mid = (l + r) / 2; tr[root].sign = 0; build(l, mid, root * 2); build(mid + 1, r, root * 2 + 1); tr[root].sign = tr[root * 2].sign + tr[root * 2 + 1].sign; tr[root].max = max(tr[root * 2].max, tr[root * 2 + 1].max); tr[root].min = min(tr[root * 2].min, tr[root * 2 + 1].min);}void push_up(int root){ root = root / 2; while(root) { tr[root].sign = tr[root * 2].sign + tr[root * 2 + 1].sign; tr[root].max = max(tr[root * 2].max, tr[root * 2 + 1].max); tr[root].min = min(tr[root * 2].min, tr[root * 2 + 1].min); root /= 2; } return ;}void update(int num, int val, int root){ int l = tr[root].l; int r = tr[root].r; if(l == r && l == num) { tr[root].max = val; tr[root].min = val; if(front[l]) if(front[l] == l && val < tr[dis[l-1]].max) { tr[dis[l-1]].sign++, tr[root].sign--; front[l] = l-1; back[l-1] = l-1; push_up(dis[l-1]); } else if(front[l] == l-1 && val > tr[dis[l-1]].max) { tr[dis[l-1]].sign--, tr[root].sign++; front[l] = l; back[l-1] = l; push_up(dis[l-1]); } if(back[l]) if(back[l] == l && val < tr[dis[l+1]].max) { tr[dis[l+1]].sign++, tr[root].sign--; back[l] = l+1; front[l+1] = l+1; push_up(dis[l+1]); } else if(back[l] == l+1 && val > tr[dis[l+1]].max) { tr[dis[l+1]].sign--, tr[root].sign++; back[l] = l; front[l+1] = l; push_up(dis[l+1]); } return ; } int mid = (l + r) / 2; if(mid >= num) update(num, val, root * 2); else update(num, val, root * 2 + 1); tr[root].sign = tr[root * 2].sign + tr[root * 2 + 1].sign; tr[root].max = max(tr[root * 2].max, tr[root * 2 + 1].max); tr[root].min = min(tr[root * 2].min, tr[root * 2 + 1].min); return ;}int query(int val, int root){ if(val < tr[root].min) return 0; if(tr[root].max <= val) return tr[root].sign; return query(val, root * 2) + query(val, root * 2 + 1);}int main(){ int t; cin >> t; for(int Case = 1; Case <= t; Case ++) { printf("Case #%d:\n", Case); int n, sum = 0, sum2 = 0; cin >> n; int pre = -1000000000; init(); for(int i = 0; i < n; i++) { int ta, tb; scanf("%d %d", &ta, &tb); if(tb != 0) { pre = ta; h[++sum] = tb; change[i] = sum; for(int j = sum2; j >= 1; j--) if(dis[j] > ta - pos[j]) near[sum]++, near[sum-1]--, dis[j] = ta - pos[j]; else if(dis[j] == ta - pos[j]) { if(h[sum] > h[sum-1]) near[sum]++, near[sum-1]--, back[sum-1]=sum, front[sum] = sum; else front[sum] = sum-1, back[sum-1] = sum-1; } else break; } else { near[sum]++; dis[++sum2] = ta - pre; pos[sum2] = ta; } } build(1, sum, 1); cin >> n; for(int i = 0; i < n; i++) { char c; cin >> c; getchar(); //cout << c << endl << endl; if(c == ‘U‘) { int t1, t2; scanf("%d %d", &t1, &t2); update(change[t1], t2, 1); } else { int t1; scanf("%d", &t1); printf("%d\n", query(t1, 1)); } } }}
C学的不好确实很蛋疼，我的字符输入用的是cin。。。
这要是TLE了我可就真的没辙了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。