线段树

题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换 n 次以后得到的数列中，逆序对的个数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let’s find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let’s consider the following test:

题目链接 题意：圆上，询问任意一段弧中，任意两点的距离+两点的权值和的最大值。 思路： 1.环先拆成串，复制 1..n 到后面，变成 1..2n。 化简公式： 2 * h[u] + 2 * h[v] + dist(u, v) = 2 * h[v] + d[1] + d[2] + … + d[v-1] + 2 * h[u] - (d[1] + d[2] + … + d[u-1]).

题目链接 题意：有 n 个数，每次可以删除掉数值相同并且所在位置成等差数列（只删 2 个数或者只删 1 个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出 m 个询问，每个询问一个区间 [l,r]，问删光区间 [l,r] 中的数最少需要的操作次数。

题目链接 题意：给出 n 个数，然后 m 个询问，每个询问一个区间 [l,r]，问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST 4File Name :code/spoj/dquery.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=3E4+7; 32const int M=2E5+7; 33int n,Q; 34int a[N]; 35int tree[N<<2]; 36map<int,int>mp; 37struct node 38{ 39 int l,r; 40 int id; 41 bool operator < (node b)const 42 { 43 if (r==b.r) return l<b.l; 44 return r<b.r; 45 } 46}q[M]; 47void PushUp( int rt) 48{ 49 tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 50} 51void update( int p,int sc,int l,int r ,int rt) 52{ 53 if (l==r) 54 { 55 tree[rt]+=sc; 56 return; 57 } 58 int m = (l+r)>>1; 59 if (p<=m) update(p,sc,lson); 60 else update(p,sc,rson); 61 PushUp(rt); 62} 63int query(int L,int R,int l,int r,int rt) 64{ 65 if (L<=l&&r<=R) return tree[rt]; 66 int m = (l+r)>>1; 67 int ret = 0 ; 68 if (L<=m) ret += query(L,R,lson); 69 if (R>=m+1) ret+=query(L,R,rson); 70 return ret; 71} 72int ans[M]; 73int main() 74{ 75 #ifndef ONLINE_JUDGE 76 freopen("code/in.txt","r",stdin); 77 #endif 78 cin>>n; 79 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 80 cin>>Q; 81 for ( int i = 1 ; i <= Q ; i++) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i ; 82 sort(q+1,q+Q+1); 83 int cur = 1; 84 for ( int i = 1 ; i <= Q ; i++) 85 { 86 for ( ; cur <= q[i].r ; cur++) 87 { 88 if (mp[a[cur]]) update(mp[a[cur]],-1,1,n,1); 89 mp[a[cur]] = cur; 90 update(mp[a[cur]],1,1,n,1); 91 } 92 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1); 93 } 94 for ( int i = 1 ; i <= Q ; i++) printf("%d\n",ans[i]); 95 #ifndef ONLINE_JUDGE 96 fclose(stdin); 97 #endif 98 return 0; 99} 之后补一个主席树的做法

题目链接 题意：题意是由伪代码给出的，手算模拟了一下（noip 初赛即视感），题意大概是说，给出两个数组 a 和 b，a 数组长度为 n，b 数组长度为 len，然后从 a 中截取连续的 len 个元素，称为数组 s，如果存在一种方法使得 s 中元素和 b 中的元素一一对应且每组和都大于等于 h，则称这个 s 是合法的。现在问 a 中有多少个合法的 s。 具体来说，对于样例 5 2 10 5 3 1 8 5 5 7

1756: Vijos1083 小白逛公园 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss] Description # 小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。 一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。 那么，就请你来帮小白选择公园吧。

题目链接 题意：给出n个数，m个修改，每次修改后询问整个区间的最大连续子段。 思路：考虑一段区间，分成左右两个子区间，这段区间的最大子段有三种情况：只在左区间中，只在右区间中，既在左区间中又在右区间中。前两种很好维护，对于后一种，我们新增加线段树的两个域，mxl,mxr，分别表示一个区间中包含左端点在的最大字段和（也就是最大前缀和），和一个区间中包含右端点在的最大子段和（也就是最大后缀和），然后对于最大子段既在左区间又在右区间的情况，只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。

题目链接 题意：给出两个排列，定义 ord(p) 为排列 p 的顺序（字典序从小到大），定义 perm(x) 为顺序为 x 的排列，现在要求 1 ≤ n ≤ 200 000 思路：首先去学了一下康托展开和逆展开，其实就是对于这种排列问题的一个比较省空间的 hash 函数？

题目链接 题意：给出一个长度为n的数列，每个位置是0或者1，给出q个操作，操作有两种类型，分别是将一段区间中反转，和询问当前某位置是0还是1 思路：lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数，初始为0.然后查询的时候，根据被翻转次数的奇偶性确定答案。

题目链接 题意：现在有N个骑士进行M轮PK…现在告诉这M轮是谁站在台上…其将l~r所存在的骑士都打败..而若一个骑士被打败..就出局了..也就是不存在了…请输出每个骑士是被哪个骑士打败的(最后的胜利者输出0)…保证有解..

题目链接 题意：给出两个数组，每个数组 n 个数，分别为 a 和 b，给出 m 个操作，操作有两种类型，第一种是给出 x,y,k，表示从 a 数组的 x 坐标开始复制 k 个数到 b 数组的 y 到 y+k-1。 第二种操作是给出 x，询问当前 b[x] 是多少。

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉，顺便问一句。。a divide b 是 a除b，也就是b除以a,b/a的意思嘛23333）

题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。 思路：对于这种要求三个数满足条件的题目，老司机的经验是考虑中间那个数，这道题也不例外。

题目链接 题意：定义_f_(l, r, x)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that_f_(1, i, a__i) > f(j, n, a__j). 思路：可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]]，其实预处理的过程就是离散化的过程呢。。。

题目链接 题意：给出n和m，初始给出1«n个数，先相邻的两个数进行或操作（a[1]^a[2],a[3]^a[4]…），得到的新数列再相邻的两个数进行异或操作。

题目链接 题意： 在二维坐标平面内进行 n (1 ≤ n ≤ 2·10^5) 次操作。一共有三种类型操作。 1.add x,y 将点 (x,y) 加进坐标系。 2.remove x,y 将点 (x,y) 移除。 3.find x,y 找到点 (x,y) 右上角的点 (xp>x,yp>y)。如果有多个输出 x 最小的。如果还有多个输出 y 最小的。

poj 2828 题目链接 题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1)

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。 一开始借鉴了 clj 的 pointer 写法，wjmzbmr’s code 直接 MLE，看来也许只能在 cf 上用。 下面是 MLE 的代码： 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月18日 星期四 18时40分24秒 4File Name :code/hdu/1754.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27using namespace std; 28const double eps = 1E-8; 29const int dx4[4]={1,0,0,-1}; 30const int dy4[4]={0,-1,1,0}; 31const int inf = 0x3f3f3f3f; 32const int N=2E5+7; 33int a[N],n,m; 34int _max( int x,int y) 35{ 36 if (x==-1||y==-1) 37 return x==-1?y:x; 38 return a[x]>a[y]?x:y; 39} 40struct Tree 41{ 42 Tree *pl,*pr; 43 int l,r,mx; 44 void update() 45 { 46 mx = _max(pl->mx,pr->mx); 47 } 48 Tree(int l,int r) : 49 l(l),r(r) 50 { 51 if ( l + 1 == r) 52 { 53 mx = l ; 54 return ; 55 } 56 pl = new Tree(l,(l+r)>>1); 57 pr = new Tree((l+r)>>1,r); 58 update(); 59 } 60 void change(int p,int x) 61 { 62 if (p < l|| p>=r) return; 63 if (l+1==r) 64 { 65 a[l] = x; 66 return ; 67 } 68 pl->change(p,x); 69 pr->change(p,x); 70 update(); 71 } 72 int queryMax(int L,int R) 73 { 74 if (L <= l && r <= R) return mx; 75 if (L>=r || l >=R) 76 return -1; 77 return _max(pl->queryMax(L,R),pr->queryMax(L,R)); 78 } 79}*rt; 80int main() 81{ 82 #ifndef ONLINE_JUDGE 83 freopen("code/in.txt","r",stdin); 84 #endif 85 while (~scanf("%d%d",&n,&m)) 86 { 87 ms(a,0); 88 for ( int i = 0 ; i < n ; i++) scanf("%d",a+i); 89 rt = new Tree(0,n); 90 while (m--) 91 { 92 char opt[3]; 93 int x,y; 94 scanf("%s %d %d",opt,&x,&y); 95 x--; 96 if (opt[0]=='Q') 97 printf("%d\n",a[rt->queryMax(x,y)]); 98 else rt->change(x,y); 99 } 100 } 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105} 关于线段树的理解，见代码注释：

嘛，终于下定决心搞定线段树了。 之前几次都是被lazy标记卡住，这次大概不会了吧2333 放一些学习资料，最后比较zkw线段树和普通线段树的区别。 codeforces上非递归线段树讲解 （其实就是zkw吧） 线段树进阶（各种花式技巧） 找到了一篇非常赞的tutorial（含lazy标记） 链接

http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小） 思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。