HDU 4831 Scenic Popularity

思路：先预处理每个休息区左边和右边的景区位置，然后每次修改直接修改即可，查询的时候枚举每个位置计算出热度
代码：

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int N = 10005; int t, n, q; struct Point { int x, val, l, r; void read() { scanf("%d%d", &x, &val); } } p[N]; int cal(int i) { int ans = 0; if (p[i].val != 0) return p[i].val; if (p[i].l != i) ans = p[p[i].l].val; if (p[i].r != i) { if (p[i].l == i) { ans = p[p[i].r].val; return ans; } if (p[i].x - p[p[i].l].x > p[p[i].r].x - p[i].x) ans = p[p[i].r].val; else if (p[i].x - p[p[i].l].x == p[p[i].r].x - p[i].x) ans = max(ans, p[p[i].r].val); } return ans; } int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) { p[i].read(); p[i].l = p[i].r = i; } for (int i = 1; i < n; i++) { if (p[i].val == 0) { if (p[p[i - 1].l].val == 0) p[i].l = i; else p[i].l = p[i - 1].l; } } for (int i = n - 2; i >= 0; i--) { if (p[i].val == 0) { if (p[p[i + 1].r].val == 0) p[i].r = i; else p[i].r = p[i + 1].r; } } scanf("%d", &q); char s[10]; int a, b; printf("Case #%d:\n", ++cas); while (q--) { scanf("%s", s); if (s[0] == 'Q') { scanf("%d", &a); int ans = 0; for (int i = 0; i < n; i++) { if (cal(i) <= a) ans++; } printf("%d\n", ans); } else { scanf("%d%d", &a, &b); p[a].val = b; } } } return 0; }