二次联通门 :
/* luogu P1908 逆序对 权值线段树 + 离散化 + 指针版线段树。。。 把所有数离散化后将其作为下标建空树 对于每次插入的数字x， 查找x+1到max区间的数字存在的个数， 并将这个个数加入答案， 然后插入这个数字 最后输出答案 %%Menci的线段树。。。6到一定境界了。。。 */#include#include #define Max 40080void read (int &now){ now = 0; register char word = getchar (); while (word < '0' || word > '9') word = getchar (); while (word >= '0' && word <= '9') { now = now * 10 + word - '0'; word = getchar (); }}inline int min (int a, int b){ return a < b ? a : b;}inline int max (int a, int b){ return a > b ? a : b;}struct Segment_Tree_Date{ Segment_Tree_Date *Left, *Right; Segment_Tree_Date () { Left = NULL; Right = NULL; key = 0; } int l, r; int key; int Mid;};Segment_Tree_Date *Root;class Segment_Tree_Type{ public : void Build (Segment_Tree_Date *&now, int l, int r) { now = new Segment_Tree_Date; now->l = l; now->r = r; if (l == r) return ; now->Mid = l + r >> 1; Build (now->Left, l, now->Mid); Build (now->Right, now->Mid + 1, r); } void Change_Single (Segment_Tree_Date *&now, int pos) { if (now->l == now->r) { now->key++; return ; } if (pos <= now->Mid) Change_Single (now->Left, pos); else if (pos > now->Mid) Change_Single (now->Right, pos); now->key = now->Left->key + now->Right->key; } int Query (Segment_Tree_Date *&now, int l, int r) { if (l <= now->l && r >= now->r) return now->key; int res = 0; if (l <= now->Mid) res += Query (now->Left, l, min (now->Mid, r)); if (r > now->Mid) res += Query (now->Right, max (l, now->Mid + 1), r); return res; }}Tree;int N, M;int date[Max];int rank_number[Max];int main (int argc, char *argv[]){ read (N); for (int i = 1; i <= N; i++) { read (date[i]); rank_number[i] = date[i]; } std :: sort (date + 1, date + 1 + N); int Size = std :: unique (date + 1, date + 1 + N) - date - 1; int Answer = 0; Tree.Build (Root, 1, Size); for (int i = 1; i <= N; i++) { rank_number[i] = std :: lower_bound (date + 1, date + 1 + Size, rank_number[i]) - date; if (rank_number[i] < Size) Answer += Tree.Query (Root, rank_number[i] + 1, Size); Tree.Change_Single (Root, rank_number[i]); } printf ("%d", Answer); return 0;}