oToToT的code收藏區

題目連結: 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://acm.csie.org/ntujudge/problem.php?id=903 有趣的好題，想了很久只想的到樹鍊剖分的作法，被雷了才知道更好的做法QQ 對於全子樹加一其實很簡單，就把樹壓扁後把$[in[x], out[x]]$全部加一就好，然後詢問時則單點詢問邊即可。但是另外兩個操作就會變得很難做，所以要用另外一種方式想，考慮一條邊若或被加值，則一定是因為它下面的點有被加值，所以其實對最底下的點加值即可，然後為了怕太上面的人也會被算到，記得超過最頂之後要再減一以免多算，這樣就變成單點加值區間查詢了。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; class BIT1{ #define lowbit(x) ((x)&(-(x))) private: int arr[N], size; inline int query(int x){ int r=0; while(x){ r+=arr[x]; x-=lowbit(x); } return r; } public: inline void init(int x){ fill(arr, arr+size, 0); size=x; } inline int query(int l, int r){ // 1-base (l, r] return query(r)-query(l); } inline void add(int x,...

題目連結: http://tioj.infor.org/problems/1272 給定一棵樹，然後要求詢問某個節點的值是偶數或奇數，或者對一整顆子樹加一。不妨把樹壓平後，透過進入時間戳與出去的時間戳，得到一個區間$[in[x], out[x])$，而其實這個區間就是x的子樹，所以發現要對子樹加值就是對那個區間加值，而查詢則是查$in[x]$。把問題轉成單點查詢區間加值後，其實一個BIT就可以做到了。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; class BIT{ private: int arr[N], size=0; inline int lowbit(int x){ return x&-x; } public: void init(int s){ fill(arr, arr+s, 0); size=s; } //1-base (l, r] void add(int l, int r, int v){ add(l, -v); add(r, v); } void add(int s, int v){ while(s){ arr[s]+=v; s-=lowbit(s); } } int query(int x){ int r=0; while(x<size){ ...

題目連結: http://tioj.infor.org/problems/1493 本題要求在樹上對一個節點單點加值或是問一個節點及其子樹的和，顯然直接照著做會TLE，所以不妨考慮把樹壓扁後的序列，修改一個節點的值就是對序列作單點修改，問子樹的話也會剛好是一個連續的區間，所以就直接作區間詢問就好。單點修改，區間查詢就是一個BIT支援的操作，所以就開三個BIT把三種果實維護好即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int, int> PII; #define FF first #define SS second const int N = 1000000 + 5; vector<int> g[N]; int st[N], ed[N], timer=1; void dfs(int,int); struct BIT{ int arr[2*N]; inline int lowbit(int x){ return x&(-x); } void add(int w, int c){ while(w<=timer){ arr[w]+=c; w+=lowbit(w); } } int query(int l, int r){ return query(r-1) - query(l-1); } int query(int w){ int r=0; while(w){ r+=arr[w]; w-=lowbit(w); } return r;...

題目連結: http://tioj.infor.org/problems/1228 本題是建中資訊校內複賽題，當時我在寫的時候完全不會線段樹甚麼的，所以我那時是直接照著做，然後稍微二分搜一下他的區間，就拿到了第二組subtask，因此比完之後我一直以為這題很簡單，直到聽完題解說要把樹壓扁、開BIT，我才發現原來沒有想像中的簡單。 --以上廢話-- 本題把樹壓扁後就變成單點修改區間查詢的序列問題了，但什麼是把樹壓扁呢，在本題中可以發現我們會修改以及查詢的其實都是邊權，所以其實可以用一定的方法幫這些邊編號，而因為我們在查區間和時是用DFS的方法去跑，所以不妨就用DFS時碰到邊的順序幫它編號，但記得要開個mapping能讓它之後詢問跟修改時知道要對幾號做動作，大概就醬吧。 p.s本題記憶體有點卡，不能寫線段樹，只能寫BIT(至少我就醬被梗了一段時間 #include <bits/stdc++.h> using namespace std; #define N 1000000 #define lowbit(x) ((x)&-(x)) struct node{ int child,val; }; struct dian{ int l,r; }; vector<node> tree[N+5]; dian dianMap[N+5]; int bianMap[N+5]; int BIT[N+5]; int n,q; int counter=0; int arr[N]; void foldTree(int); void buildBIT(); void edit(int,int); inline int sum(int); int query(int,int); int main(){ scanf("%d%d",&n,&q); for(int i=0;i<n-1;i++){ int a,b,m; scanf("%d%d...