oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1998 可以發現其實每個IP都是一個32-bit的東東，所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1，而我們要詢問一堆IP是不是在一堆區間內，其實就直接把那些區間當作區間加值，那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大，要先離散化掉就是了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int M = 200000 + 5; const int N = 300000 + 5; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } } lisan; ...

題目連結: http://tioj.infor.org/problems/1410 裸的區間加值，查詢全部最大值問題。因為沒有奇怪的修改之類的，所以我們可以直接用個簡單的技巧，先插入兩個小標記之後再往後推過去一遍的作法做，而這題應為值域太大要先離散話，或是向我一樣懶懶的直接開個map解決他。 #include <bits/stdc++.h> using namespace std; map<long long,int> mp; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ long long l, r; cin>>l>>r; mp[l]++; mp[r+1]--; } int cur = 0, ans = 0; for(auto i: mp){ cur += i.second; ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/contest/198/problem/E 被雷了才會QQ 會發現其實他是個圓並不重要，重要的其實是距離，所以不妨把每個人的座標轉換成跟原點的距離，這樣的話每次詢問就變成詢問一個距離內質量小於k的數有誰，而我們其實也不用一次把一坨東西拉出來，只要一次拉一個就好，反正最多拉n個，複雜度不會太慘。而這樣其實就是詢問一個前綴極值就可達到這件事，所以就開個BIT套個單調的queue之類的就可以做到這件事了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define ALL(x) begin(x), end(x) #define FF first #define SS second const int N = 250000 + 5; const lld INF = 1LL<<31; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } inline lld ...

題目連結: 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{...

題目連結: 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://tioj.infor.org/problems/1045 原本看到的時候想用線段樹直接揍他，結果寫一寫覺得卡卡的，然後就被嗆說幹嘛用線段樹做了QQ。想了想才發現可以離散化後直接對序列操作，複雜度$O(N^2)$，也就是把序列乘二或除二，然後算一下他的變化量來維護整段的總和。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; #define ALL(x) (x).begin(), (x).end() const int N = 10000 + 1; 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 get(int x){ return distance(v.begin(), lower_bound(ALL(v),x)); } inline int inv_get(int x){ return v[x]; } } li; struct Opt{ int pos, l, r, v; }; vector<Opt> op...