本文主要是介绍hdu1556（树状数组/线段树，区间修改，点查询），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
//题目大意：一段序列，给连续的一段涂色，问某个点被涂的次数#include <iostream>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define N 100010using namespace std;int sum[N<< 2], add[N<< 2];
int a[N], n, x, y;void pushup(int k) { sum[k]= sum[k<< 1]+ sum[k<< 1| 1]; }void build(int l, int r, int k)
{if(l== r) { sum[k]= a[l]; return; }int m= (l+ r)>> 1;build(l, m, k<< 1);build(m+ 1, r, k<< 1| 1);pushup(k);
}void pushdown(int k, int ln, int rn)
{if(add[k]){add[k<< 1]+= add[k];add[k<< 1| 1]+= add[k];sum[k<< 1]+= add[k]* ln;sum[k<< 1| 1]+= add[k]* rn;add[k]= 0;}
}void update(int l, int r, int c, int ll, int rr, int k)
{if(l<= ll && r>= rr){sum[k]+= c* (rr- ll+ 1);add[k]+= c;return;}int m= (ll+ rr)>> 1;pushdown(k, m- ll+ 1, rr- m);if(l<= m) update(l, r, c, ll, m, k<< 1);if(r> m) update(l, r, c, m+ 1, rr, k<< 1| 1);pushup(k);
}int query(int l, int r, int ll, int rr, int k)
{if(l<= ll && r>= rr) return sum[k];int m= (ll+ rr)>> 1;pushdown(k, m- ll+ 1, rr- m);int ans= 0;if(l<= m) ans+= query(l, r, ll, m, k<< 1);if(r> m) ans+= query(l, r, m+ 1, rr, k<< 1| 1);return ans;
}int main()
{while(scanf("%d", &n)== 1 && n){memset(sum, 0, sizeof(sum));memset(add, 0, sizeof(add));memset(a, 0, sizeof(a));build(1, n, 1);for(int i= 0; i< n; i++){scanf("%d%d", &x, &y);update(x, y, 1, 1, n, 1);}for(int i= 1; i< n; i++) printf("%d ", query(i, i, 1, n, 1));printf("%d\n", query(n, n, 1, n, 1));}return 0;
}
这篇关于hdu1556（树状数组/线段树，区间修改，点查询）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
