题目链接：[点击打开链接](http://codeforces.com/contest/620/problem/E) 题意：给你一棵树，编号1~n，告诉你根结点是1。 每次有两个操作： 1，将以v为根的子树的结点全部染成颜色c 2，问以v为根的紫书的结点的颜色种类。 思路：如果这是一条线段的话， 那么这就是线段树的区间更新问题，而现在是一棵树。 因为告诉了根结点是1， 那么这棵树的任意一个结点的子树就是确定的， 所以我们可以用DFS的先序遍历，将所有结点重新编号，因为先序遍历的话， 任意一个结点和其子树的编号就是一条连续的线段了，在这其中维护每个结点的新编号， 和这个结点的子树中的最大编号即可。 然后就是线段树区间更新了， 由于颜色数最大60， 用long long通过位运算的 | 操作就行了， 注意对1左移的时候应该先将1转成long long再进行操作。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 400000 + 10; int T,n,m,u,v,id[maxn],a[maxn],cnt,last[maxn],b[maxn],setv[maxn<<2]; bool vis[maxn]; ll sum[maxn<<2]; vector<int> g[maxn]; void dfs(int root) { id[root] = ++cnt; vis[root] = true; int len = g[root].size(); for(int i=0;i<len;i++) { int v = g[root][i]; if(!vis[v]) { dfs(v); } } last[root] = cnt; } void PushUp(int o) { sum[o] = sum[o<<1] | sum[o<<1|1]; } void pushdown(int l, int r, int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; sum[o<<1] = sum[o<<1|1] = (1LL<<setv[o]); setv[o] = 0; } } void build(int l, int r, int o) { int m = (l + r) >> 1; setv[o] = 0; if(l == r) { sum[o] = 1LL<<b[++cnt]; return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); PushUp(o); } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { setv[o] = v; sum[o] = (1LL << v); return ; } pushdown(l, r, o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); PushUp(o); } ll query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(l, r, o); ll ans = 0; if(L <= m) ans |= query(L, R, l, m, o<<1); if(m < R) ans |= query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); g[u].clear(); } for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } memset(vis, 0, sizeof(vis)); cnt = 0; dfs(1); for(int i=1;i<=n;i++) { b[id[i]] = a[i]; } cnt = 0; build(1, n, 1); int res, v, c; while(m--) { scanf("%d",&res); if(res == 1) { scanf("%d%d",&v,&c); update(id[v], last[v], c, 1, n, 1); } else { scanf("%d",&v); ll ans = query(id[v], last[v], 1, n, 1); int cc = 0; for(int i=1;i<=61;i++) { if(ans & (1LL<<i)) cc++; } printf("%d\n",cc); } } return 0; } ~~~

题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=2397&mosmsg=Submission+received+with+ID+16736144) 题意：有3种区间操作， 将某个区间全部变成1； 将某个区间全部变成0；将某个区间的1变成0， 0变成1。 思路：前两个操作就是最基本的区间更新， 用到懒惰标记， 然而第3个操作却有些麻烦， 如果仅仅更新当前这个结点对应的大区间， 那么它所包含的小区间再次更新时就会发生错误， 错误的原因是因为标记的重叠和碰撞。  显然 ， 这就是很典型的一个问题， 处理标记碰撞的问题。    问题的核心是解决碰撞， 使得每个点每个时刻至多只有一个标记。   那么怎么办呢？我们可以在两个标记发生碰撞的时候来看看会出现什么等价的情况： 当我们要更新一个结点o时： 如果我们要进行区间更新， 那么直接覆盖而不用管原来的标记。 但是如果是区间反转的时候： 如果该结点已经有一个标记v 那么： 当v == 1， 说明该区间上一次有一次全部变成1的操作， 等价于这次全部变成0， 所以懒惰标记最终变成0. 当v == 0，同理， 懒惰标记最终变成1. 当v == 2，说明该区间上一次有一个全部反转的操作还没有实现， 等价于这次不反转， 所以懒惰标记最终变成-1 当v == -1，说明该区间上一次没有操作， 等价于这次需要反转， 懒惰标记最终为2 其实就是一个等价转换而已， 当碰撞多了还将涉及一个处理的顺寻问题。 还有一点， 如果你是在更新结点v时就更新了sum[v]， 那么在等价转换的时候还涉及到sum[v]的更新问题， 不要想错了。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 1024010; int T,n,m,q,l,r,kase=0,sum[maxn<<2],setv[maxn<<2],a[maxn],cnt = 0; void PushUp(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; } void pushdown(int l, int r, int o) { if(setv[o] != -1) { int m = (l + r) >> 1; if(setv[o] == 1) { sum[o<<1] = (m - l + 1); sum[o<<1|1] = (r - m); setv[o<<1] = setv[o<<1|1] = setv[o]; } else if(setv[o] == 0) { sum[o<<1] = 0; sum[o<<1|1] = 0; setv[o<<1] = setv[o<<1|1] = setv[o]; } else { if(setv[o<<1] == 1) { setv[o<<1] = 0; sum[o<<1] = 0; } else if(setv[o<<1] == 0) { setv[o<<1] = 1; sum[o<<1] = (m - l + 1); } else if(setv[o<<1] == 2) setv[o<<1] = -1, sum[o<<1] = m - l + 1 - sum[o<<1]; else { setv[o<<1] = 2; sum[o<<1] = m - l + 1 - sum[o<<1]; } if(setv[o<<1|1] == 1) { setv[o<<1|1] = 0; sum[o<<1|1] = 0; } else if(setv[o<<1|1] == 0) { setv[o<<1|1] = 1; sum[o<<1|1] = (r - m); } else if(setv[o<<1|1] == 2) setv[o<<1|1] = -1, sum[o<<1|1] = r - m - sum[o<<1|1]; else { setv[o<<1|1] = 2; sum[o<<1|1] = r - m - sum[o<<1|1]; } } setv[o] = -1; } } void build(int l, int r, int o) { int m = (l + r) >> 1; setv[o] = -1; if(l == r) { ++cnt; if(a[cnt]) sum[o] = 1; else sum[o] = 0; return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); PushUp(o); } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { if(v == 1) { sum[o] = (r - l + 1); setv[o] = 1; } else if(v == 0) { sum[o] = 0; setv[o] = 0; } else { if(setv[o] == 1) { setv[o] = 0; sum[o] = 0; } else if(setv[o] == 0) { setv[o] = 1; sum[o] = r - l + 1; } else if(setv[o] == -1) { setv[o] = 2; sum[o] = r - l + 1 - sum[o]; } else setv[o] = -1, sum[o] = r - l + 1 - sum[o]; } return ; } pushdown(l, r, o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); PushUp(o); } int query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(l, r, o); int ans = 0; if(L <= m) ans += query(L, R, l, m, o<<1); if(m < R) ans += query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } char s[100]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&m); int n = 0; for(int i=0;i<m;i++) { scanf("%d%s",&cnt,s); int len = strlen(s); while(cnt--) { for(int j=0;j<len;j++) { a[++n] = s[j] - '0'; } } } cnt = 0; build(1, n, 1); scanf("%d",&q); printf("Case %d:\n",++kase); int cc = 0; while(q--) { scanf("%s%d%d",s,&l,&r); l++; r++; if(s[0] == 'F') update(l, r, 1, 1, n, 1); else if(s[0] == 'E') update(l, r, 0, 1, n, 1); else if(s[0] == 'I') update(l, r, 2, 1, n, 1); else printf("Q%d: %d\n",++cc, query(l, r, 1, n, 1)); } } return 0; } ~~~

题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=2520&mosmsg=Submission+received+with+ID+16730468) 题意：从1~k的所有排列中找到第n个排列， n由公式给出。 思路：可以发现， 这个公式就是康托展开公式（康托展开百科：[点击打开链接](http://baike.baidu.com/link?url=iyF_OrLBeETDKSZo-iY8M5MHQeJ0UZLkczMNtJ0t61rr-mpn_rHa0qeMlmHfv252mRIQIu7OEw6ldXVriCCDZ_)）。 那么s[i]的意思就是i个数中当前数排在第几。 如此， 可以用二分+树状数组快速求解， 和一道BC题目神似。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 50000 + 10; int T,n,v,m,c[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += c[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { c[x] += d; x += x & -x; } } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); memset(c, 0, (n+1)*sizeof(c[0])); for(int i=1;i<=n;i++) { add(i, 1); } for(int i=1;i<=n;i++) { scanf("%d",&v); v++ ; int l = 1, r = n, m ; while(r > l) { m = (l + r)/2; if(sum(m) >= v) r = m; else l = m + 1; } printf("%d%c", l , i == n ? '\n' : ' '); add(l, -1); } } return 0; } ~~~

题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=502&page=show_problem&problem=3673) 题意：依次建n个建筑， 每个建筑有3个信息，宽度：[l, r]， 和高度h， 要求求出每个建筑刚建完时最高的部分的区间长度之和。 思路：就是维护线段树区间最值， 然而有一个问题， 因为不能更新比当前高度大的区间，所以最坏的情况下要更新到所有点， 因此要加一个懒惰标记，表示该区间是否被完全覆盖，覆盖值是多少。  另外由于是区间问题， 会产生区间端点的麻烦， 所以我们把线段树中的每一个点当作一个长度为1的区间， 比如i这个点， 当成是[i, i+1)这个区间。  细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,m,maxv[maxn<<2],setv[maxn<<2],ans; struct node { int l, r, h; }a[maxn]; void PushUp(int o) { maxv[o] = max(maxv[o<<1], maxv[o<<1|1]); } void build(int l, int r, int o) { int m = (l + r) >> 1; maxv[o] = 0; setv[o] = 0; if(l == r) return ; build(l, m, o<<1); build(m+1, r, o<<1|1); } void pushdown(int l, int r, int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; maxv[o<<1] = maxv[o<<1|1] = setv[o]; setv[o] = 0; } } void update(int L, int R, int h, int l, int r, int o) { int m = (l + r) >> 1; if(setv[o] && maxv[o] > h) return ; if(L <= l && r <= R) { if(maxv[o] <= h) { maxv[o] = h; setv[o] = h; ans += r - l + 1; return ; } } if(l == r) return ; pushdown(l, r, o); if(L <= m) update(L, R, h, l, m, o<<1); if(m < R) update(L, R, h, m+1, r, o<<1|1); PushUp(o); } int main() { while(~scanf("%d",&T) && T) { while(T--) { scanf("%d",&n); int m = 0; for(int i=0;i<n;i++) { scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h); m = max(m, a[i].r); } build(1, m, 1); ans = 0; for(int i=0;i<n;i++) { update(a[i].l, a[i].r-1, a[i].h, 1, m, 1); } printf("%d\n",ans); } } return 0; } ~~~

题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=4259&mosmsg=Submission+received+with+ID+16725571) 题意： 有编号1~n的n个影碟从上到下排列， 每次取一个影碟并把其放在最上面， 求每次取之前该影碟前面有多少个影碟。 取出影碟， 将该位置-1即可， 容易想到用树状数组来维护， 但是还要放到最前面。 其实解决方法很简单， 就是把数组开大一点， 前面留出足够大的空间， 不断更新位置即可。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 200000 + 10; int T,n,v,m,bit[maxn],pos[maxn>>1]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n + m) { bit[x] += d; x += x & -x; } } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(bit, 0, (n+m+1)*sizeof(bit[0])); int cnt = m; for(int i=1;i<=n;i++) { pos[i] = i+m; add(pos[i], 1); } for(int i=0;i<m;i++) { scanf("%d",&v); printf("%d%c", sum(pos[v]-1), i == m-1 ? '\n' : ' '); add(pos[v], -1); pos[v] = cnt--; add(pos[v], 1); } } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=1436) 题意：n条竖直线段，如果两条线段之间可见（即可以用一条水平线段连接而不触碰其他线段），则称它们可见。 如果三条线段任意两条都可见， 则称它们为a triangle of segments， 求a triangle of segments的个数 思路： 一开始真没想到n^3的复杂度可以过。。。  如果这样的话， 问题的关键就是怎样判断任意两个线段是否可见。 那么如果对y坐标建立区间， 这就成了线段树的区间覆盖问题。 另外， 由于是用点代替线段， 所以对于”可见“这个问题， 就会出现问题， 比如  有三条线段[1,4]、[1,2]、[3,4]， 则在[1,4]区间中可以看见3条线段， 即可以通过[2,3]的空隙看见第一条线段。   解决方法很简单， 把坐标扩大2倍就行了，这样[1,2]变成[2,4]，[3,4]变成[6,8]，空出了一个5。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 8000 + 10; int T,n,t,q,l,r,c,col[maxn<<3],y[maxn<<1]; bool vis[maxn][maxn]; struct node { int ly, ry, x; node(int l=0, int r=0, int xx=0):ly(l),ry(r),x(xx) {} bool operator < (const node& rhs) const { return x < rhs.x || (x == rhs.x && ly < rhs.ly); } }a[maxn]; void pushdown(int o) { if(col[o] >= 0) { col[o<<1] = col[o<<1|1] = col[o]; col[o] = -1; } } void update(int L, int R, int c, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { col[o] = c; return ; } pushdown(o); if(L <= m) update(L, R, c, l, m, o<<1); if(m < R) update(L, R, c, m+1, r, o<<1|1); } void query(int L, int R, int id, int l, int r, int o) { int m = (l + r) >> 1; if(col[o] >= 0) { vis[id][col[o]] = true; return ; } if(l == r) return ; if(L <= m) query(L, R, id, l, m, o<<1); if(m < R) query(L, R, id, m+1, r, o<<1|1); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int m = 0; for(int i=0;i<n;i++) { scanf("%d%d%d",&a[i].ly, &a[i].ry, &a[i].x); m = max(m, max(a[i].ly, a[i].ry)); } sort(a, a+n); memset(col, -1, sizeof(col)); memset(vis, false, sizeof(vis)); for(int i=0;i<n;i++) { int l = a[i].ly; int r = a[i].ry; query(2*l, 2*r, i, 0, 2*m, 1); update(2*l, 2*r, i, 0, 2*m, 1); } int ans = 0; for(int i=n-1;i>=0;i--) { for(int j=i-1;j>=0;j--) { if(vis[i][j]) { for(int k=j-1;k>=0;k--) { if(vis[i][k] && vis[j][k]) ++ans; } } } } printf("%d\n",ans); } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=2777) 题意：两种操作， 一个是区间修改， 一个是区间查询颜色种类数。 该题因为要不断的求某个区间的颜色种类数， 我们可以用位运算的并来实现。 其他的就是线段树区间修改的经典操作了。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,t,q,l,r,c,sum[maxn<<2],setv[maxn<<2]; void PushUp(int o) { sum[o] = sum[o<<1] | sum[o<<1|1]; } void pushdown(int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; sum[o<<1] = sum[o<<1|1] = (1<<setv[o]); setv[o] = 0; } } void build(int l, int r, int o) { int m = (l + r) >> 1; setv[o] = 0; sum[o] = (1<<1); if(l == r) return ; build(l, m, o<<1); build(m+1, r, o<<1|1); } void update(int L, int R, int c, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { sum[o] = (1 << c); setv[o] = c; return ; } pushdown(o); if(L <= m) update(L, R, c, l, m, o<<1); if(m < R) update(L, R, c, m+1, r, o<<1|1); PushUp(o); } int query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(o); int ans = 0; if(L <= m) ans |= query(L, R, l, m, o<<1); if(m < R) ans |= query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } char s[10]; int main() { scanf("%d%d%d",&n, &t, &q); build(1, n, 1); while(q--) { scanf("%s",s); if(s[0] == 'C') { scanf("%d%d%d",&l, &r, &c); update(min(l,r), max(l,r), c, 1, n, 1); } else { scanf("%d%d",&l, &r); int ans = query(min(l,r), max(l,r), 1, n, 1), cnt = 0; for(int i=1;i<=t;i++) { if(ans & (1<<i)) ++cnt; } printf("%d\n",cnt); } } return 0; } ~~~

该题很容易想到求概率的转移方程：用d[i][j]表示第i步，走到j点的概率。 但是该题的k高达1e9，所以按照套路，要用矩阵相乘来优化。 第一次写矩阵相乘， 大概的意思就是利用矩阵实现递推， 并且因为每次递推的过程一样， 所以就相当于右乘这个矩阵的k次方。 用矩阵快速幂即可。 矩阵相乘这个问题， 大概可以看成， 矩阵中的每个元素表示到该点的概率， 那么另一个矩阵就是DP矩阵， 表示当前一步到各点的概率， 矩阵相乘就等于下一步到各点的概率（矩阵乘法的意义）。 另外， 要对答案进行1e9+5次方再取模， 如果最后取模， 那么将对分母Y进行取模后再次方再取模， 这是和原问题不等价的， 所以解决方法是按照乘法取模公式， 先对矩阵元素提前处理该操作。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 1000000000 + 7; const int maxn = 1000 + 10; ll T,n,q,u,k,m,x,y,cnt[maxn]; vector<ll> g[maxn]; typedef vector<ll> vec; typedef vector<vec> mat; mat mul(mat &a, mat &b) { mat c(a.size(), vec(a.size())); for(int i=1;i<=n;i++) { for(int k=1;k<=n;k++) { for(int j=1;j<=n;j++) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod; } } } return c; } mat pow(mat a, ll k) { mat b(a.size(), vec(a.size())); for(int i=1;i<=n;i++) { b[i][i] = 1; } while(k > 0) { if(k & 1) b = mul(b, a); a = mul(a, a); k >>= 1; } return b; } ll mod_pow(ll x, ll n, ll mod) { ll res = 1; while(n > 0) { if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { while(~scanf("%I64d%I64d",&n,&m)) { for(int i=1;i<=n;i++) g[i].clear(); memset(cnt, 0, sizeof(cnt)); mat a(n+3, vec(n+3)); for(int i=0;i<m;i++) { scanf("%I64d%I64d",&x,&y); g[y].push_back(x); a[y][x] = 1; cnt[x]++; } for(int i=1;i<=n;i++) { cnt[i] = mod_pow(cnt[i], 1000000005, mod); } for(int i=1;i<=n;i++) { int len = g[i].size(); for(int k=0;k<len;k++) { a[i][g[i][k]] = (a[i][g[i][k]] * cnt[g[i][k]]) % mod; } } scanf("%I64d",&q); while(q--) { scanf("%I64d%I64d",&u,&k); mat hehe = pow(a, k); for(int i=1;i<=n;i++) { printf("%I64d ", hehe[i][u]); } printf("\n"); } } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=3233) 题意：求S[k] = A + A^2 + ..... + A^k 利用矩阵快速幂可以很快的求出A矩阵的k次方， 但是该题是求和， 如果还按照原来的方法， 将要计算k次， 复杂度无法承受。 我们可以构造一个矩阵   （A  0）                                            （E  E） 此时令S[k] = E + A + A^2 + ..... + A^(k-1) 那么  ( A^k )     ( A   0)(A^(k-1))        (A   0 )^k (E)               =                                =                                        (S[k] )      (E   E)(S[k-1] )          (E   E )     (0) 那么， 我们只要计算出S[k+1] = E + A + .... + A^k 然后将对角线元素-1就行了。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 10007; const int maxn = 100; int T,n,m,k; typedef vector<int> vec; typedef vector<vec> mat; mat mul(mat &a, mat &b) { mat c(a.size(), vec(a[0].size())); for(int i = 0; i < a.size(); i++) { for(int k = 0; k < b.size(); k++) { for(int j = 0; j < b[0].size(); j++) { c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % m; } } } return c; } mat pow(mat a, ll n) { mat b(a.size(), vec(a[0].size())); for(int i = 0; i < a.size(); i++) { b[i][i] = 1; } while(n > 0) { if(n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { scanf("%d%d%d",&n,&k,&m); mat a(2*n, vec(2*n)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&a[i][j]); } } for(int i=n;i<2*n;i++) { for(int j=0;j<2*n;j++) if(i - n == j || i == j) a[i][j] = 1; } a = pow(a, k+1); for(int i=n;i<2*n;i++) { for(int j=0;j<n;j++) { if(i - n == j) a[i][j] = (a[i][j] - 1 + m) % m; printf("%d%c",a[i][j], j == n-1 ? '\n' : ' '); } } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=3734) 题意：个n个方块涂色， 只能涂红黄蓝绿四种颜色，求最终红色和绿色都为偶数的方案数。 该题我们可以想到一个递推式 。   设a[i]表示到第i个方块为止红绿是偶数的方案数， b[i]为红绿恰有一个是偶数的方案数， c[i]表示红绿都是奇数的方案数。 那么有如下递推可能： 递推a[i+1]：1.到第i个为止都是偶数，且第i+1个染成蓝或黄；2.到第i个为止红绿恰有一个是奇数，并且第i+1个方块染成了奇数对应的颜色。 递推b[i+1]：1.到第i个为止都是偶数，且第i+1个染成红或绿；2.到第i个为止红绿恰有一个是奇数，并且第i+1个方块染成了蓝或黄；3.到第i个方块为止红火绿都是奇数，并且第i+1个染成红火绿。 递推c[i+1]：1.到第i个为止红绿恰有一个是奇数， 并且第i+1个方块染成偶数对应的颜色；2.到第i个为止红绿都是奇数，并且第i+1个方块染成蓝或黄。 即a[i+1] = 2*a[i] + b[i];     b[i+1] = 2*a[i] + 2*b[i] + 2*c[i];     c[i+1] = b[i] + 2*c[i]; 因为DP的过程中，每一步都是在重复上一个过程， 所以可以用矩阵相乘来优化算法。 将上述递推式写成矩阵相乘的形式： { a[i] }      {2  1  0}^i{a[0] } { b[i] }  = {2  2  2}   {b[0] } { c[i] }     {0  1  2}   {c[0] } 然后用矩阵快速幂就可以了。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 10007; const int maxn = 100; ll T,n,m; typedef vector<int> vec; typedef vector<vec> mat; mat mul(mat &a, mat &b) { mat c(a.size(), vec(a[0].size())); for(int i = 0; i < a.size(); i++) { for(int k = 0; k < b.size(); k++) { for(int j = 0; j < b[0].size(); j++) { c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % mod; } } } return c; } mat pow(mat a, ll n) { mat b(a.size(), vec(a[0].size())); for(int i = 0; i < a.size(); i++) { b[i][i] = 1; } while(n > 0) { if(n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { scanf("%d",&T); mat a(3, vec(3)); while(T--) { scanf("%lld",&n); a[0][0] = 2; a[0][1] = 1; a[0][2] = 0; a[1][0] = 2; a[1][1] = 2; a[1][2] = 2; a[2][0] = 0; a[2][1] = 1; a[2][2] = 2; a = pow(a, n); printf("%d\n",a[0][0]); } return 0; } ~~~

题目链接：[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=5606) 题意：一棵树，权值只有0和1，找到每个点与之相距最近的点的个数， （包括这个点自己，也就是说，等价于找每个点与之相距为0的点的个数）。 用并查集乱搞就行了， 如果边权为0就合并集合， 并在集合的根节点上维护一个信息：该集合中点的个数。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,m,ans[maxn],p[maxn]; struct node { int a, b, c; node(int aa=0, int bb=0, int cc=0):a(aa), b(bb), c(cc) {} }a[maxn]; int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); } int solve() { for(int i=1;i<=n;i++) p[i] = i, ans[i] = 1; for(int i=1;i<=n-1;i++) { int x = _find(a[i].a), y = _find(a[i].b); if(!a[i].c) { p[x] = y; ans[y] += ans[x]; } } int hehe = 0; for(int i=1;i<=n;i++) { int x = _find(i); hehe ^= ans[x]; } return hehe; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n-1;i++) { scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c); } printf("%d\n",solve()); } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=2528) 题意：在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报。 该题是线段树区间修改+离散化的应用。 不难想到， 每次对一个最长10^7的线段进行线段树的区间修改， 最后统计。 线段树的复杂度是log10^7， 应该不会超时， 但是会超内存。 所以想到要离散化， 将区间端点值有映射成一个尽量小的值。 但是该题求的是覆盖情况， 如果按照单纯的点对点的离散化， 那样会出现错误答案。 例如：  依次贴[1,10], [1,3], [5,10] ， 离散化后1->1, 3->2, 5->3, 10->4 那么第一次让离散后的区间[1,4]变成1，第二次让[1,2]变成2，第三次让[3,4]变成3，那么最终答案成了2， 其实是3。 问题之所在就在于：小的区间不会覆盖大区间的所有部分。 解决方法就是在相邻区间端点大于1时再添加一个二者中间的数当作“空白”区域。 不会离散化的先学学离散化吧， 一般用二分来维护比较简单。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 11111; int T,n,ans,setv[maxn<<4],X[maxn<<3]; bool vis[maxn]; struct node { int l, r; node(int ll=0, int rr=0):l(ll), r(rr) {} bool operator < (const node& rhs) const { return l < rhs.l || (l == rhs.l && r < rhs.r); } }a[maxn]; void pushdown(int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; setv[o] = 0; } } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { setv[o] = v; return ; } pushdown(o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); } void query(int l, int r, int o) { int m = (l + r) >> 1; if(setv[o]) { if(!vis[setv[o]]) { vis[setv[o]] = true; ++ans; } return ; } if(l == r) return ; query(l, m, o<<1); query(m+1, r, o<<1|1); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int cnt = 0; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); X[cnt++] = a[i].l; X[cnt++] = a[i].r; } sort(X, X+cnt); cnt = unique(X, X+cnt) - X; int m = cnt; for(int i=1;i<cnt;i++) { if(X[i] > X[i-1]+1) X[m++] = X[i] + 1; } sort(X, X + m); memset(vis, false, (n+1)*sizeof(vis[0])); memset(setv, 0, sizeof(setv)); for(int i=1;i<=n;i++) { int lc = lower_bound(X, X + m, a[i].l) - X + 1; int rc = lower_bound(X, X + m, a[i].r) - X + 1; update(lc, rc, i, 1, m, 1); } ans = 0; query(1, m, 1); printf("%d\n",ans); } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=3468) 题意：区间加减，区间求和。 该题是线段树区间增减和区间求和的模板题。 和区间修改值一样， 在每个结点上维护一个之前加减的值， 那么每次经过一个结点时， 当前结点一定已经拥有所有结点信息。 每次递归前下传结点信息，这就是所谓的懒惰标记。  细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,l,r,q,v; ll sum[maxn<<2],addv[maxn<<2]; char s[10]; void push_up(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; } void build(int l, int r, int o) { int m = (l + r) >> 1; addv[o] = 0; if(l == r) { scanf("%lld",&sum[o]); return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); push_up(o); } void pushdown(int o, int l, int r) { if(addv[o]) { int m = (l + r) >> 1; addv[o<<1] += addv[o]; addv[o<<1|1] += addv[o]; sum[o<<1] += (ll)(m - l + 1) * addv[o]; sum[o<<1|1] += (ll)(r - m) * addv[o]; addv[o] = 0; } } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { addv[o] += v; sum[o] += (ll)v * (r - l + 1); return ; } pushdown(o, l, r); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); push_up(o); } ll query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; //当前结点一定已经拥有所有的标记 } ll ans = 0; pushdown(o, l, r); if(L <= m) ans += query(L, R, l, m, o<<1); if(m < R) ans += query(L, R, m+1, r, o<<1|1); push_up(o); return ans; } int main() { while(~scanf("%d%d",&n,&q)) { build(1, n, 1); while(q--) { scanf("%s%d%d",s,&l,&r); if(s[0] == 'Q') { printf("%lld\n",query(l, r, 1, n, 1)); } else { scanf("%d",&v); update(l, r, v, 1, n, 1); } } } return 0; } ~~~

题目链接：[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=1698) 题意： 输入一个n表示一段长度为n的区间，有n个编号为1~n的点，初始值全部为1。 有q个操作， 每个操作有3个数：l，r，v表示将区间l~r的所有元素修改为v。 求经过q次修改后的整个区间的值之和。 该题是最典型的线段树区间修改问题， 需要用到所谓的懒惰标记。   听起来挺难的，其实非常简单， 其原理如下： 因为修改很多值， 如果还是按照原来的更新方法， 每个结点更新一次的话，速度实在太慢。 那么能不能一起更新呢？  答案是肯定的。 一个点一个点的更新之所以慢 ， 是因为每个被该点影响的点我们都需要更新。   为了能”顺便“更新， 我们在每个结点上多维护一个信息， 表示上次该区间修改的值是多少，然后然后每次向下更新之前将标记更新到儿子结点。 对于线段树， 只要理解好每个结点表示一个不重复不交叉的区间， 就差不多可以理解其更新过程了。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 100000 + 10; int T,n,l,r,v,q,sum[maxn*4],cur[maxn*4],kase=0; void push_up(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; } void pushdown(int o, int l, int r) { if(cur[o]) { int m = (l + r) >> 1; cur[o<<1] = cur[o<<1|1] = cur[o]; sum[o<<1] = (m - l + 1) * cur[o]; sum[o<<1|1] = (r - m) * cur[o]; cur[o] = 0; } } void build(int l, int r, int o) { int m = (l + r) >> 1; cur[o] = 0; if(l == r) { sum[o] = 1; return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); push_up(o); } void update(int L, int R, int c, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { cur[o] = c; sum[o] = c * (r - l + 1); return ; } pushdown(o, l, r); if(L <= m) update(L, R, c, l, m, o<<1); if(m < R) update(L, R, c, m+1, r, o<<1|1); push_up(o); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); build(1,n,1); while(q--) { scanf("%d%d%d",&l,&r,&v); update(l, r, v, 1, n, 1); } printf("Case %d: The total value of the hook is %d.\n",++kase , sum[1]); } return 0; } ~~~

题目链接：[点击打开链接](http://poj.org/problem?id=2886) 题意：一共n个人， 从第k个人开始， 这个人离队并且指定向左或向右第v个人离队， 依次下去， 求得分最高的人是谁。 第p个人离队， 将得到G（p）分， G（p）是可以整除p的所有数。 对于可以被i整除的数的个数， 我们可以通过枚举每一个数的倍数， 预先处理出来。 该题直接模拟就好， 因为每次都一定有一个人出队， 所以要枚举n次 ， 对于每次， 要计算具体是哪个人出队， 这个可以用数学推导很快的算出来是当前队列的第几个人， 要找到这个人我们可以用二分+树状数组来优化算法。  复杂度O(n*logn*logn) 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 500000 + 10; int T,n,k,m,cnt[maxn] = {0},bit[maxn]; struct node { char s[20]; int v; }a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } void init() { for(int i=1;i<=500000;i++) { for(int j=i;j<=500000;j+=i) { cnt[j]++; } } } int erfen(int x) { int l = 1, r = n, mid; while(r > l) { mid = (r + l) >> 1; if(sum(mid) >= x) r = mid; else l = mid + 1; } return r; } int main() { init(); while(~scanf("%d%d",&n,&k)) { memset(bit, 0, (n+1)*sizeof(bit[0])); int maxv = cnt[1]; for(int i=1;i<=n;i++) { scanf("%s%d",a[i].s,&a[i].v); maxv = max(maxv, cnt[i]); add(i, 1); } int now = k, nxt = k, _cnt = 1; while(true) { int nn = n - _cnt; m = a[now].v; if(cnt[_cnt] == maxv) { printf("%s %d\n",a[now].s,cnt[_cnt]); break; } if(m > 0) nxt = (nxt - 1 + m % nn) % nn; else nxt = ((nxt + m)%nn + nn)%nn; if(nxt == 0) nxt = nn; add(now, -1); now = erfen(nxt); _cnt++; } } return 0; } ~~~

转载自：NotOnlySuccess的博客 【完全版】线段树 很早前写的那篇线段树专辑至今一直是本博客阅读点击量最大的一片文章,当时觉得挺自豪的,还去pku打广告,但是现在我自己都不太好意思去看那篇文章了,觉得当时的代码风格实在是太丑了,很多线段树的初学者可能就是看着这篇文章来练习的,如果不小心被我培养出了这么糟糕的风格,实在是过意不去,正好过几天又要给集训队讲解线段树,所以决定把这些题目重新写一遍,顺便把近年我接触到的一些新题更新上去~;并且学习了splay等更高级的数据结构后对线段树的体会有更深了一层,线段树的写法也就比以前飘逸,简洁且方便多了.     在代码前先介绍一些我的线段树风格:   maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍 lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示 以前的写法是另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行,只需要写函数的时候多两个参数,结合lson和rson的预定义可以很方便 PushUP(int rt)是把当前结点的信息更新到父结点 PushDown(int rt)是把当前结点的信息更新给儿子结点 rt表示当前子树的根(root),也就是当前所在的结点 整理这些题目后我觉得线段树的题目整体上可以分成以下四个部分:   单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来 hdu1166 敌兵布阵 题意:O(-1) 思路:O(-1) 线段树功能:update:单点增减 query:区间求和 ~~~ #include <cstdio> #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 55555; int sum[maxn<<2]; void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void build(int l,int r,int rt) { if (l == r) { scanf("%d",&sum[rt]); return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt); } void update(int p,int add,int l,int r,int rt) { if (l == r) { sum[rt] += add; return ; } int m = (l + r) >> 1; if (p <= m) update(p , add , lson); else update(p , add , rson); PushUP(rt); } int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret; } int main() { int T , n; scanf("%d",&T); for (int cas = 1 ; cas <= T ; cas ++) { printf("Case %d:\n",cas); scanf("%d",&n); build(1 , n , 1); char op[10]; while (scanf("%s",op)) { if (op[0] == 'E') break; int a , b; scanf("%d%d",&a,&b); if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1)); else if (op[0] == 'S') update(a , -b , 1 , n , 1); else update(a , b , 1 , n , 1); } } return 0; } ~~~ hdu1754 I Hate It 题意:O(-1) 思路:O(-1) 线段树功能:update:单点替换 query:区间最值 ~~~ #include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 222222; int MAX[maxn<<2]; void PushUP(int rt) { MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]); } void build(int l,int r,int rt) { if (l == r) { scanf("%d",&MAX[rt]); return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt); } void update(int p,int sc,int l,int r,int rt) { if (l == r) { MAX[rt] = sc; return ; } int m = (l + r) >> 1; if (p <= m) update(p , sc , lson); else update(p , sc , rson); PushUP(rt); } int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return MAX[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret = max(ret , query(L , R , lson)); if (R > m) ret = max(ret , query(L , R , rson)); return ret; } int main() { int n , m; while (~scanf("%d%d",&n,&m)) { build(1 , n , 1); while (m --) { char op[2]; int a , b; scanf("%s%d%d",op,&a,&b); if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1)); else update(a , b , 1 , n , 1); } } return 0; } ~~~ hdu1394 Minimum Inversion Number 题意:求Inversion后的最小逆序数 思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解 线段树功能:update:单点增减 query:区间求和 ~~~ #include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 5555; int sum[maxn<<2]; void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void build(int l,int r,int rt) { sum[rt] = 0; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } void update(int p,int l,int r,int rt) { if (l == r) { sum[rt] ++; return ; } int m = (l + r) >> 1; if (p <= m) update(p , lson); else update(p , rson); PushUP(rt); } int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret; } int x[maxn]; int main() { int n; while (~scanf("%d",&n)) { build(0 , n - 1 , 1); int sum = 0; for (int i = 0 ; i < n ; i ++) { scanf("%d",&x[i]); sum += query(x[i] , n - 1 , 0 , n - 1 , 1); update(x[i] , 0 , n - 1 , 1); } int ret = sum; for (int i = 0 ; i < n ; i ++) { sum += n - x[i] - x[i] - 1; ret = min(ret , sum); } printf("%d\n",ret); } return 0; } ~~~ hdu2795 Billboard 题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子 思路:每次找到最大值的位子,然后减去L 线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了) ~~~ #include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 222222; int h , w , n; int MAX[maxn<<2]; void PushUP(int rt) { MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]); } void build(int l,int r,int rt) { MAX[rt] = w; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } int query(int x,int l,int r,int rt) { if (l == r) { MAX[rt] -= x; return l; } int m = (l + r) >> 1; int ret = (MAX[rt<<1] >= x) ? query(x , lson) : query(x , rson); PushUP(rt); return ret; } int main() { while (~scanf("%d%d%d",&h,&w,&n)) { if (h > n) h = n; build(1 , h , 1); while (n --) { int x; scanf("%d",&x); if (MAX[1] < x) puts("-1"); else printf("%d\n",query(x , 1 , h , 1)); } } return 0; } ~~~ 练习:   poj2828 Buy Tickets poj2886 Who Gets the Most Candies? /*************************************************************************************************************/ 成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候   hdu1698 Just a Hook 题意:O(-1) 思路:O(-1) 线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息)   ~~~ #include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 111111; int h , w , n; int col[maxn<<2]; int sum[maxn<<2]; void PushUp(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void PushDown(int rt,int m) { if (col[rt]) { col[rt<<1] = col[rt<<1|1] = col[rt]; sum[rt<<1] = (m - (m >> 1)) * col[rt]; sum[rt<<1|1] = (m >> 1) * col[rt]; col[rt] = 0; } } void build(int l,int r,int rt) { col[rt] = 0; sum[rt] = 1; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt); } void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { col[rt] = c; sum[rt] = c * (r - l + 1); return ; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (R > m) update(L , R , c , rson); PushUp(rt); } int main() { int T , n , m; scanf("%d",&T); for (int cas = 1 ; cas <= T ; cas ++) { scanf("%d%d",&n,&m); build(1 , n , 1); while (m --) { int a , b , c; scanf("%d%d%d",&a,&b,&c); update(a , b , c , 1 , n , 1); } printf("Case %d: The total value of the hook is %d.\n",cas , sum[1]); } return 0; } ~~~ poj3468 A Simple Problem with Integers 题意:O(-1) 思路:O(-1) 线段树功能:update:成段增减 query:区间求和 ~~~ #include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 #define LL long long const int maxn = 111111; LL add[maxn<<2]; LL sum[maxn<<2]; void PushUp(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void PushDown(int rt,int m) { if (add[rt]) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; sum[rt<<1] += add[rt] * (m - (m >> 1)); sum[rt<<1|1] += add[rt] * (m >> 1); add[rt] = 0; } } void build(int l,int r,int rt) { add[rt] = 0; if (l == r) { scanf("%lld",&sum[rt]); return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt); } void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { add[rt] += c; sum[rt] += (LL)c * (r - l + 1); return ; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson); PushUp(rt); } LL query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; LL ret = 0; if (L <= m) ret += query(L , R , lson); if (m < R) ret += query(L , R , rson); return ret; } int main() { int N , Q; scanf("%d%d",&N,&Q); build(1 , N , 1); while (Q --) { char op[2]; int a , b , c; scanf("%s",op); if (op[0] == 'Q') { scanf("%d%d",&a,&b); printf("%lld\n",query(a , b , 1 , N , 1)); } else { scanf("%d%d%d",&a,&b,&c); update(a , b , c , 1 , N , 1); } } return 0; } ~~~ poj2528 Mayor’s posters 题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报 思路:这题数据范围很大,直接搞超时+超内存,需要离散化: 离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了 所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多 而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱) 给出下面两个简单的例子应该能体现普通离散化的缺陷: 1-10 1-4 5-10 1-10 1-4 6-10 为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10] 如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了. 线段树功能:update:成段替换 query:简单hash ~~~ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 11111; bool hash[maxn]; int li[maxn] , ri[maxn]; int X[maxn*3]; int col[maxn<<4]; int cnt; void PushDown(int rt) { if (col[rt] != -1) { col[rt<<1] = col[rt<<1|1] = col[rt]; col[rt] = -1; } } void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { col[rt] = c; return ; } PushDown(rt); int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson); } void query(int l,int r,int rt) { if (col[rt] != -1) { if (!hash[col[rt]]) cnt ++; hash[ col[rt] ] = true; return ; } if (l == r) return ; int m = (l + r) >> 1; query(lson); query(rson); } int Bin(int key,int n,int X[]) { int l = 0 , r = n - 1; while (l <= r) { int m = (l + r) >> 1; if (X[m] == key) return m; if (X[m] < key) l = m + 1; else r = m - 1; } return -1; } int main() { int T , n; scanf("%d",&T); while (T --) { scanf("%d",&n); int nn = 0; for (int i = 0 ; i < n ; i ++) { scanf("%d%d",&li[i] , &ri[i]); X[nn++] = li[i]; X[nn++] = ri[i]; } sort(X , X + nn); int m = 1; for (int i = 1 ; i < nn; i ++) { if (X[i] != X[i-1]) X[m ++] = X[i]; } for (int i = m - 1 ; i > 0 ; i --) { if (X[i] != X[i-1] + 1) X[m ++] = X[i] + 1; } sort(X , X + m); memset(col , -1 , sizeof(col)); for (int i = 0 ; i < n ; i ++) { int l = Bin(li[i] , m , X); int r = Bin(ri[i] , m , X); update(l , r , i , 0 , m , 1); } cnt = 0; memset(hash , false , sizeof(hash)); query(0 , m , 1); printf("%d\n",cnt); } return 0; } ~~~ poj3225 Help with Intervals 题意:区间操作,交,并,补等 思路: 我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含) U:把区间[l,r]覆盖成1 I:把[-∞,l)(r,∞]覆盖成0 D:把区间[l,r]覆盖成0 C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换 S:[l,r]区间0/1互换   成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作 很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了 所以当一个节点得到覆盖标记时把异或标记清空 而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记   开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间) 线段树功能:update:成段替换,区间异或 query:简单hash ~~~ #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 131072; bool hash[maxn]; int cover[maxn<<2]; int XOR[maxn<<2]; void FXOR(int rt) { if (cover[rt] != -1) cover[rt] ^= 1; else XOR[rt] ^= 1; } void PushDown(int rt) { if (cover[rt] != -1) { cover[rt<<1] = cover[rt<<1|1] = cover[rt]; XOR[rt<<1] = XOR[rt<<1|1] = 0; cover[rt] = -1; } if (XOR[rt]) { FXOR(rt<<1); FXOR(rt<<1|1); XOR[rt] = 0; } } void update(char op,int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { if (op == 'U') { cover[rt] = 1; XOR[rt] = 0; } else if (op == 'D') { cover[rt] = 0; XOR[rt] = 0; } else if (op == 'C' || op == 'S') { FXOR(rt); } return ; } PushDown(rt); int m = (l + r) >> 1; if (L <= m) update(op , L , R , lson); else if (op == 'I' || op == 'C') { XOR[rt<<1] = cover[rt<<1] = 0; } if (m < R) update(op , L , R , rson); else if (op == 'I' || op == 'C') { XOR[rt<<1|1] = cover[rt<<1|1] = 0; } } void query(int l,int r,int rt) { if (cover[rt] == 1) { for (int it = l ; it <= r ; it ++) { hash[it] = true; } return ; } else if (cover[rt] == 0) return ; if (l == r) return ; PushDown(rt); int m = (l + r) >> 1; query(lson); query(rson); } int main() { cover[1] = XOR[1] = 0; char op , l , r; int a , b; while ( ~scanf("%c %c%d,%d%c\n",&op , &l , &a , &b , &r) ) { a <<= 1 , b <<= 1; if (l == '(') a ++; if (r == ')') b --; if (a > b) { if (op == 'C' || op == 'I') { cover[1] = XOR[1] = 0; } } else update(op , a , b , 0 , maxn , 1); } query(0 , maxn , 1); bool flag = false; int s = -1 , e; for (int i = 0 ; i <= maxn ; i ++) { if (hash[i]) { if (s == -1) s = i; e = i; } else { if (s != -1) { if (flag) printf(" "); flag = true; printf("%c%d,%d%c",s&1?'(':'[' , s>>1 , (e+1)>>1 , e&1?')':']'); s = -1; } } } if (!flag) printf("empty set"); puts(""); return 0; } ~~~ 练习:   poj1436 Horizontally Visible Segments poj2991 Crane Another LCIS Bracket Sequence 区间合并 这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并   poj3667 Hotel 题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边 2 a b:将[a,a+b-1]的房间清空 思路:记录区间中最长的空房间 线段树操作:update:区间替换 query:询问满足条件的最左断点 ~~~ #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 55555; int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2]; int cover[maxn<<2]; void PushDown(int rt,int m) { if (cover[rt] != -1) { cover[rt<<1] = cover[rt<<1|1] = cover[rt]; msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1); msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1); cover[rt] = -1; } } void PushUp(int rt,int m) { lsum[rt] = lsum[rt<<1]; rsum[rt] = rsum[rt<<1|1]; if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1]; if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1]; msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1])); } void build(int l,int r,int rt) { msum[rt] = lsum[rt] = rsum[rt] = r - l + 1; cover[rt] = -1; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1; cover[rt] = c; return ; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson); PushUp(rt , r - l + 1); } int query(int w,int l,int r,int rt) { if (l == r) return l; PushDown(rt , r - l + 1); int m = (l + r) >> 1; if (msum[rt<<1] >= w) return query(w , lson); else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return m - rsum[rt<<1] + 1; return query(w , rson); } int main() { int n , m; scanf("%d%d",&n,&m); build(1 , n , 1); while (m --) { int op , a , b; scanf("%d",&op); if (op == 1) { scanf("%d",&a); if (msum[1] < a) puts("0"); else { int p = query(a , 1 , n , 1); printf("%d\n",p); update(p , p + a - 1 , 1 , 1 , n , 1); } } else { scanf("%d%d",&a,&b); update(a , a + b - 1 , 0 , 1 , n , 1); } } return 0; } ~~~ 练习:   hdu3308 LCIS hdu3397 Sequence operation hdu2871 Memory Control hdu1540 Tunnel Warfare CF46-D Parking Lot 扫描线 这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去 最典型的就是矩形面积并,周长并等题 hdu1542 Atlantis 题意:矩形面积并 思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该区间下边比上边多几个 线段树操作:update:区间增减 query:直接取根节点的值   ~~~ #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 2222; int cnt[maxn << 2]; double sum[maxn << 2]; double X[maxn]; struct Seg { double h , l , r; int s; Seg(){} Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {} bool operator < (const Seg &cmp) const { return h < cmp.h; } }ss[maxn]; void PushUp(int rt,int l,int r) { if (cnt[rt]) sum[rt] = X[r+1] - X[l]; else if (l == r) sum[rt] = 0; else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { cnt[rt] += c; PushUp(rt , l , r); return ; } int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson); PushUp(rt , l , r); } int Bin(double key,int n,double X[]) { int l = 0 , r = n - 1; while (l <= r) { int m = (l + r) >> 1; if (X[m] == key) return m; if (X[m] < key) l = m + 1; else r = m - 1; } return -1; } int main() { int n , cas = 1; while (~scanf("%d",&n) && n) { int m = 0; while (n --) { double a , b , c , d; scanf("%lf%lf%lf%lf",&a,&b,&c,&d); X[m] = a; ss[m++] = Seg(a , c , b , 1); X[m] = c; ss[m++] = Seg(a , c , d , -1); } sort(X , X + m); sort(ss , ss + m); int k = 1; for (int i = 1 ; i < m ; i ++) { if (X[i] != X[i-1]) X[k++] = X[i]; } memset(cnt , 0 , sizeof(cnt)); memset(sum , 0 , sizeof(sum)); double ret = 0; for (int i = 0 ; i < m - 1 ; i ++) { int l = Bin(ss[i].l , k , X); int r = Bin(ss[i].r , k , X) - 1; if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1); ret += sum[1] * (ss[i+1].h - ss[i].h); } printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , ret); } return 0; } ~~~ hdu1828 Picture 题意:矩形周长并 思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用lbd和rbd表示边界来辅助) 线段树操作:update:区间增减 query:直接取根节点的值 ~~~ #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 22222; struct Seg{ int l , r , h , s; Seg() {} Seg(int a,int b,int c,int d):l(a) , r(b) , h(c) , s(d) {} bool operator < (const Seg &cmp) const { return h < cmp.h; } }ss[maxn]; bool lbd[maxn<<2] , rbd[maxn<<2]; int numseg[maxn<<2]; int cnt[maxn<<2]; int len[maxn<<2]; void PushUP(int rt,int l,int r) { if (cnt[rt]) { lbd[rt] = rbd[rt] = 1; len[rt] = r - l + 1; numseg[rt] = 2; } else if (l == r) { len[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0; } else { lbd[rt] = lbd[rt<<1]; rbd[rt] = rbd[rt<<1|1]; len[rt] = len[rt<<1] + len[rt<<1|1]; numseg[rt] = numseg[rt<<1] + numseg[rt<<1|1]; if (lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;//两条线重合 } } void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { cnt[rt] += c; PushUP(rt , l , r); return ; } int m = (l + r) >> 1; if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson); PushUP(rt , l , r); } int main() { int n; while (~scanf("%d",&n)) { int m = 0; int lbd = 10000, rbd = -10000; for (int i = 0 ; i < n ; i ++) { int a , b , c , d; scanf("%d%d%d%d",&a,&b,&c,&d); lbd = min(lbd , a); rbd = max(rbd , c); ss[m++] = Seg(a , c , b , 1); ss[m++] = Seg(a , c , d , -1); } sort(ss , ss + m); int ret = 0 , last = 0; for (int i = 0 ; i < m ; i ++) { if (ss[i].l < ss[i].r) update(ss[i].l , ss[i].r - 1 , ss[i].s , lbd , rbd - 1 , 1); ret += numseg[1] * (ss[i+1].h - ss[i].h); ret += abs(len[1] - last); last = len[1]; } printf("%d\n",ret); } return 0; } ~~~ 练习   hdu3265 Posters hdu3642 Get The Treasury poj2482 Stars in Your Window poj2464 Brownie Points II hdu3255 Farming ural1707 Hypnotoad’s Secret uva11983 Weird Advertisement     线段树与其他结合练习(欢迎大家补充):   hdu3333 Turing Tree hdu3874 Necklace hdu3016 Man Down hdu3340 Rain in ACStar zju3511 Cake Robbery UESTC1558 Charitable Exchange CF85-D Sum of Medians spojGSS2 Can you answer these queries II

题目链接：[点击打开链接](http://poj.org/problem?id=2828) 题意：给n个人依次插队的情况， 要求求出最终的队伍情况。 该题可以用树状数组很方便的维护。 如果从前向后扫的话， 每次插队都会影响这个人后面的情况， 所以我们可以倒着进行， 那么最后一个人的位置就是最终位置， 对于前面的人的位置， 只受后面人的影响， 所以等价于其最终位置是第pos[i]+1个空位。   那么也就是说要快速的找到第pos[i]+1个空位。   显然， 这又可以用二分位置和树状数组维护的方法来优化算法。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 200000 + 10; int T,n,m,bit[maxn],ans[maxn]; struct node { int pre, v; }a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { while(~scanf("%d",&n)) { memset(bit, 0, (n+1)*sizeof(bit[0])); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].pre,&a[i].v); for(int i=n;i>=1;i--) { int l = 1, r = n, mid; while(r > l) { mid = (l + r) >> 1; if(mid - sum(mid) > a[i].pre) r = mid; else l = mid + 1; } ans[l] = a[i].v; add(l, 1); } printf("%d",ans[1]); for(int i=2;i<=n;i++) printf(" %d",ans[i]); printf("\n"); } return 0; } ~~~

题目链接：[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=2795) 题意： 原始序列全为w， 找到最左边的>=a的位置， 将该位置的值减去a，答案为该位置， 如果找不到符合要求的位置， 输出-1。 该题利用线段树递归特点来求其最左边的大于等于a的位置。 线段树递归的特点是从祖先结点开始自顶向下递归，访问各个元素的顺序一定是从左到右， 并且在递归之后可以顺便维护区间结点的值。 利用这个特点， 我们可以直接查询到>=a的最左边的位置。该元素变成v - a，  然后顺便维护改变了的值。 所以该题就成了维护区间最大值的线段树题目。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 200010; int T,n,w,h,a,m,maxv[maxn*4]; void push_up(int o) { maxv[o] = max(maxv[o<<1], maxv[o<<1|1]); } void build(int l, int r, int o) { int m = (l + r) >> 1; maxv[o] = w; if(l == r) return ; build(l, m, o<<1); build(m+1, r, o<<1|1); push_up(o); } int query(int v, int l, int r, int o) { int m = (l + r) >> 1, ans = 0; if(l == r) { maxv[o] -= v; return l; } if(maxv[o<<1] >= v) ans = query(v, l, m, o<<1); else ans = query(v, m+1, r, o<<1|1); push_up(o); return ans; } int main() { while(~scanf("%d%d%d",&h,&w,&n)) { if(h > n) h = n; build(1, h, 1); for(int i=0;i<n;i++) { scanf("%d",&a); if(maxv[1] < a) printf("-1\n"); else printf("%d\n",query(a, 1, h, 1)); } } return 0; } ~~~

题目链接：[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=1394) 对于求逆序数的问题， 通常用线段树或者树状数组来维护， 树状数组代码短，好写， 还是尽量写树状数组吧。 首先求出原始排列的逆序数，  那么对于每一次操作， 因为都是将当前排列的第一个数拿到最后一个位置， 所以答案就增加了所有比他大的数字个数，减小了所有比他小的数字个数。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 5000+10; int T,n,m,bit[maxn],a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { while(~scanf("%d",&n)) { memset(bit, 0, sizeof(bit)); int ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]++; ans += sum(n) - sum(a[i]); add(a[i], 1); } int cur = ans; for(int i=1;i<n;i++) { int cnt = sum(a[i]-1); cur += n - 1 - cnt - cnt; ans = min(ans, cur); } printf("%d\n",ans); } return 0; } ~~~

该题之前用树状数组写过， 最近在学习线段树， 用线段树重新写了一遍。 在学习一种新的数据结构之前， 最重要的是要理解其结构是什么样子的， 这个可以参照《算法竞赛入门经典-训练指南》P199页。  比较重要的是理解好几个变量： 1.每个结点有一个编号。   这个编号对应了其所统治的区间， 我们从线段树的祖先结点开始从上到下， 从左到右的顺序给所有结点编号，这样， 编号为i的结点其左右结点的编号就是2i和2i+1。 2.我们每次计算的m = (l + r) >> 1是当前区间[l, r]的中点， 为的是将当前区间不重复的分成两个子区间。  然后这两个子区间的结点编号又分别对应了2i 和 2i+1。 这样我们每次从祖先结点&&最大区间开始进行， 采用分治的思想， 就可以快速的进行计算了， 另外在更新操作的时候利用线段树的特点，每次递归结束之后顺带更新当前结点的值。 学习建议：  第一遍可以模仿， 建议模仿多个版本， 自己组建一个自己喜欢的代码风格，这样也有助于理解和记忆。 明白原理和过程之后， 以后尽量不要看模板， 自己手写出来， 这样可以加深理解。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 50000+10; int T,p,v,n,m,kase=0,sum[maxn<<2]; void push_up(int o) { sum[o] = sum[o<<1] + sum[o<<1|1]; } void build(int l, int r, int o) { int m = (l + r) >> 1; if(l == r) { scanf("%d",&sum[o]); return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); push_up(o); } void update(int p, int add, int l, int r, int o) { int m = (l + r) >> 1; if(l == r) { sum[o] += add; return ; } if(p <= m) update(p, add, l, m, o<<1); else update(p, add, m+1, r, o<<1|1); push_up(o); } int query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1, ans = 0; if(L <= l && r <= R) { return sum[o]; } if(m >= L) ans += query(L, R, l, m, o<<1); if(m+1 <= R) ans += query(L, R, m+1, r, o<<1|1); return ans; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); build(1,n,1); char s[10]; printf("Case %d:\n",++kase); while(~scanf("%s",s)) { if(s[0] == 'E') break; scanf("%d%d",&p,&v); if(s[0] == 'A') update(p,v,1,n,1); else if(s[0] == 'S') update(p,-v,1,n,1); else printf("%d\n",query(p,v,1,n,1)); } } return 0; } ~~~