oToToT的code收藏區

題目連結: https://tioj.infor.org/problems/2039 注意！以下是努力壓常數後過的$O(N \log N)$作法(雖然好像大家也都是$O(N \log C)$的aliens優化解)。 這裡講一下我的作法好了，首先我們將題目視成不斷將k變大並詢問當前最大是多少。若是只有一個k的時候，我們顯然是要找一組左低右高的區間$[a_l, a_r]$，那變成兩個的時候，我們發現其實有幾種可能，一種是在$l$左邊繼續找一組左低右高的區間，或是在$r$右邊找一組左低右高的區間，或是在$(l, r)$中找一組左高右低的區間，把他們的差加進答案即可。 所以我們可以用線段樹維護我們想知道某個區間內左高右低或左低右高的最大值，這樣我們就是每次從heap拿出一個最大的區間加進答案後，把它左右中三個區間同時再塞到heap裡，繼續做到直到沒有東東可以拿，或達到k就好。 不過一般的線段樹實作會TLE，所以我寫了個zkw加上自己寫heap後就可以AC了XD #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; namespace { #define FORCE_INLINE __attribute__((always_inline)) constexpr int INF = 1 << 30; constexpr int maxn = 2'000'000; template <typename T1, typename T2> struct Pair { T1 first; T2 second; }; struct V { int val, pos_small, pos_big; }; struct S { Pair<int, int> lo, hi; V v[2]; FORCE_INLINE S(Pair<int, int> small, Pair<int...

題目連結: http://codeforces.com/problemset/problem/877/E 把樹壓扁後題目就轉化成有一個01序列，並且有兩種操作：查詢區間和跟把區間的bit反轉。稍微想一下會發現線段樹可以好好做他，所以就用線段樹維護一下就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,bool> PIB; #define FF first #define SS second const int N = 200000 + 5; class SegTree{ private: PIB nodes[N<<2]; int n; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} inline void push(int l, int r, int id){ if(!nodes[id].SS) return; nodes[id].FF = r-l - nodes[id].FF; if(r-l > 1){ nodes[lc(id)].SS ^= nodes[id].SS; nodes[rc(id)].SS ^= nodes[id].SS; } nodes[id].SS = 0; } inline void pull(int l, int r, int id){ int val = 0, mid = (l+r)>>1; if(nodes[lc(id)]...

題目連結: 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://arc080.contest.atcoder.jp/tasks/arc080_c 作法滿greedy的，每次都挑字典序最小的一組pair，而且中間必定要隔偶數個數字，挑出來後就可以直接寫在前面，因為這方法其實就等價於最後再挑這兩個(因為中間隔偶數個，所以中間一定可以拿完)，不過稍微再想兩下就會發現其實還可以知道每次要挑的位置是先奇數再偶數，而且每次後面那個偶數位的一定不能超過前面拔掉的位置之一，稍微處理一下這個細節大概就可以做了。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second const int N = 200000 + 5; const int INF = 1<<30; class SegTree{ private: int size; PII nodes[4*N]; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} void build(int l, int r ,int id, PII arr[]){ if(r-l==1){ nodes[id]=arr[l]; return; } int mid=(l+r)>>1; build(l, mid, lc(id), arr); build(mid, r, rc(id), arr); nodes[id] = min(nodes[lc(id)], nodes[rc(id)]); } ...

題目連結: http://poj.org/problem?id=2104 裸的區間第K大值，曾經會過可是又忘記了，只記得關鍵字持久化，被雷了才知道。原來就是原本的序列第K大是直接用樹上的節點作二分搜，但是區間的話就變成要用$[L,R]$的和做節點二分搜，而要算$[L,R]$的和，其實就用持久化線段樹把$roots[R]-roots[L]$即可。 #include <iostream> #include <vector> #include <algorithm> #include <cassert> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100000 + 5; const int MEM = 2000000; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline int size(){return v.size();} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } inline int inv_get(int x){return v[x];} } lisan; ...

題目連結: http://www.spoj.com/problems/DQUERY/ 被雷了才會做QQ，本題有兩種做法，一種是持久化線段樹，作法滿特別的(?，序列要將在每個時間點最遠的各個數字改成一，其他改成零(如圖) 那詢問一個$[l, r]$時，就只要對第$r$時間點的線段樹詢問$[l, r]$即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 30000 + 5; const int MEM = 900000; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline int size(){return v.size();} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } } lisan; class SegTree{ private: struct Node{ int val, lc, rc; Node(){val=0;lc=-1;rc=-1;} };...

題目連結: http://tioj.infor.org/problems/1223 前面一直狂WA，但總覺得我的想法沒有錯，最後才發現是某個小地方做錯了QQ 想法大概就是把原本不行的區間轉成可以的區間，然後塞到線段樹，其中線段樹維護的是每個點往右最遠可以到哪裡，並且記錄一下是在第幾號的時候有最遠，那查詢也變得很容易，因為就只要單點查那個點最遠可以到哪裡就好了。 把步行區間轉可以區間的部分是害我一直WA掉的點，原本以為轉法就是排序好一堆$[L_i, R_i)$，接著看$[R_{i-1}, L_i]$是否合法($ R_{i-1} 另外線段樹的部分因為最後是要取最大值，修改也都是取最大值，所以其實可以直接在節點上修改，然後詢問時把路徑上的所有節點取max就好。 p.s 值域有點大所以要先離散化 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100000 + 10; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int size(){return v.size();} inline int get(int x){ ...

題目連結: http://poj.org/problem?id=1769 一開始用cin有把連結斷開還是吃了個TLE QQ。 回到正題，本題我個人的一開始的想法其實是看看某個線段插到線段樹後可以幹嘛，後來想一想後發現有點DP的fu，狀態大概就是$dp[i]$為最遠轉移到i時的最小值，那新增一條線段的時候其實就是查$[l,r]$之間的最小值，然後把$r$那個點設成先前查到的最小值+1，因為$\displaystyle dp[i] = \min_{l \leq j \leq r}dp[j]+1 $，不過實際在寫的時候要再跟原值取個min，因為有可能r被覆蓋很多次之類的。 #include <cstdio> #include <algorithm> using std::min; const int N = 50000 + 10; const int INF = 1<<30; class SegTree{ private: int nodes[N<<2], size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} void build(int l, int r, int id){ nodes[id] = INF; if(r-l>1){ int mid=(l+r)>>1; build(l, mid, lc(id)); build(mid, r, rc(id)); } } void modify(int ql, int qr, int v, int l, int r, int id){ if(qr <= l o...

題目連結: http://poj.org/problem?id=3468 裸的線段樹，區間加值、區間查和，不過也可以用BIT做掉，不過我不太會QQ #include <iostream> #include <utility> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 100000 + 5; class SegTree{ private: PLL nodes[N<<2]; int size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} inline void push(int l, int r, int id){ if(r-l>1){ nodes[lc(id)].FF += nodes[id].FF; nodes[rc(id)].FF += nodes[id].FF; } nodes[id].SS += nodes[id].FF * (r-l); nodes[id].FF=0; } inline void pull(int l, int r,int id){ int mid=(l+r)>>1; lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l); lld rr =...

題目連結: http://tioj.infor.org/problems/1316 一開始想錯方向，以為是有一堆開頭跟結尾，然後要選一些之類的...。卡了超久做不出來後，才發現其實它就是一堆線段，然後要選一堆線段，使得同一個位置只能最多被覆蓋到兩次。那其實就直接greedy選右界最靠近左邊的就好了(因為越短，表示你越可以選到後面的)。 這裡寫了個線段樹，來判斷可不可以插入，不過應該可以不用，然後也可以直接$O(N)$的做這個操作XD #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second const int N = 4000 + 5; class SegTre{ private: struct node{ int flag=0, val=0; } nodes[N<<3]; int size; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} inline void push(int l, int r, int id){ if(r-l > 1){ nodes[lc(id)].flag+=nodes[id].flag; nodes[rc(id)].flag+=nodes[id].flag; } nodes[id].val += nodes[id].flag; nodes[id].flag=0; } inline void pull(int id){ ...

題目連結: http://tioj.infor.org/problems/1224 一個非常經典的掃描線應用，利用掃描線把原本二維的問題降成一維的，再搭配線段樹，就可以做到$O(n log n)$的複雜度，不過本題的線段樹要存的東東有點特別，我想了一段時間才寫出比較精簡的版本，不然我原本是寫讓他存區間和，可是這樣就會再詢問有幾個非空節點上有困難，所以不妨再存一個值紀錄當前非空節點有幾個，而顯然當你懶標記值大於0時整段都被覆蓋，所以就是整段的長度，而沒有整段被覆蓋的時候，那當然就是去看小孩的值囉，不過仔細想想就會發現區間和根本沒用，所以就砍掉他吧XDD #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back typedef long long lld; typedef pair<int, int> PII; #define FF first #define SS second const int N = 1000000 + 5; struct bian{ PII pos; int cnt; bool operator<(const bian& a)const{ return pos<a.pos; } }; vector<pair<int,bian>> E; class SegTree{ private: struct Node{ int len=0; int cnt=0; } arr[4*N]; void pull(int id, int l, int r){ if(arr[id].cnt) arr[id].len = r - l; ...

題目連結: http://tioj.infor.org/problems/1952 或 http://codeforces.com/problemset/problem/558/E 本題要每次都對某個區間按小到大或大到小排序，那字串排序大概會想到counting sort，不難發現counting sort就是在對那個區間的a-z各自求和，之後再按順序填回去。這時就會有似曾相似的感覺了吧......吧，那就是區間求和跟區間修改，顯然用線段樹可以做到，不過要開a-z共26顆線段樹，每次要修改前就區間查和然後先歸零再把前面都改成一，最後輸出的時候就每個字元都查詢一下是哪一個，大概就這樣吧 p.s 第一次寫區間修改區間查詢的線段樹，怎麼運用懶標記卡了有點久ww 再p.s 其實這題有更快的作法，詳細解法可以看看 余柏敘大大的code #include <bits/stdc++.h> using namespace std; #define unset -1 #define N 100000 struct segNode{ int l,r,val; int m; }; void buildTree(int,int,int,int); segNode segTree[26][N*4]; void modify(int, int, int, int, int); int query(int, int, int, int); void push(int,int); int gVal(int,int); int main(){ int n,m; scanf("%d%d",&n,&m); char str[N+5]; scanf("%s",str); for(int i=0;i<26;i++){ buildTree(i,0,n,0); } for(int i=0;i<n;i++){ modify...