oToToT的code收藏區

題目連結: http://codeforces.com/contest/854/problem/E 賽中還有一個多小時時一看到這題就知道該怎麼做了，然而想太快有許多細節忽略掉就爛掉了(後來還因為沒開long long又de了約莫5個小時QQ)。 因為保證每一行每一列都只會有一個格子被塗黑，所以其實可以把整張網格壓成一個序列(如同他給的資料一樣)，那這樣詢問一個矩形內有幾個黑格子時其實就是詢問一個區間大於A小於B的數字有幾個，可能很多人直覺就直接持久話做掉，不過我是想到先前寫過的一個做法(歸併樹)：開一顆線段樹，樹上節點是一個排序好的序列，查詢那個比K大的數字時就直接二分搜一下就好了，而若要再查小於B的數字，其實可以用扣掉比B+1大的做法做就好了。 這樣我們就會做查詢一個矩形內黑色的數量了，剩下該怎麼算的問題了。仔細想想(其實好像根本就是高一組合題)後，發現可以用扣的，那問題轉化為給你一個中間挖掉一塊的矩形，問你可以湊出幾個矩形，那顯然就是挖掉那塊矩形的上下左右一大塊都是不能用的，但是扣掉這些後左上、左下、右上、右下會被多扣，再加回來就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() typedef long long lld; const int N = 200000 + 5; class SegTree{ private: vector<int> nodes[4*N]; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} int size; void build(int l, int r, int arr[], int id){ if(r-l > 1){ int mid=(l+r)>>1; ...

題目連結: http://www.spoj.com/problems/DQUERY/ 本題的另外一種解法，構造方式與 上一種 不同，這裡的構造方式是將每個相同的數字由左至右連邊(如圖) 那這樣對於一個詢問$[L, R]$，就變成詢問$[L,R]$中大於$R$的數有多少個，因為每個數字最終必須往外伸出去。 而詢問$[L,R]$中大於$R$的數有多少個，其實可以用一種跟線段樹很像的做法做，節點存的是排序好的$[L,R]$，那詢問就直接二分搜就好，不過建立的過程退化成$O(n log n)$查詢則變成$O( n log^2 n)$ #include <iostream> #include <vector> #include <algorithm> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back const int N = 30000 + 5; const int INF = 1<<30; class LiSan{ private: vector<int> v; public: void init(){v.clear();} void insert(int x){v.PB(x);} int size(){return v.size();} void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } } lisan; class SegTree{...