oToToT的code收藏區

題目連結: https://tioj.infor.org/problems/1975 首先本題要可以觀察到對於只有即時性工作時我們很簡單的就是計算他重疊最多的部分是多少，而對於非即時性工作則是要透過由deadline由小到大排後，每次選取被加值最少的那些不重疊區間來分配，最後計算最大值。 合併這兩個思考之後就可以發現本題變成一個用treap可以維護的題目了XD #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; const int C = 1000000 + 5; namespace Treap{ #define sz( x ) ( ( x ) ? ( ( x )->size ) : 0 ) #define sm( x ) ( ( x ) ? ( ( x )->sum ) : 0 ) struct node{ int size, cnt, sum; uint32_t pri; node *lc, *rc; node(): size( 0 ), cnt( 0 ), sum( 0 ), pri( rand() ), lc( nullptr ), rc( nullptr ) {} node( int x ): size( 1 ), cnt( x ), sum( x ), pri( rand() ), lc( nullptr ), rc( nullptr ) {} void pull() { sum = cnt; if ( lc ) sum += lc->sum; if ( rc ) sum += rc->sum; size = 1; if ( lc ) size += lc-...

題目連結: http://tioj.infor.org/problems/1827 不難發現本題可以對答案二分搜，因為S有單調性，那驗證的時候就是要驗證一個區域是不是有至少k個數小於S，我原本想說用個BIT套treap之類的，但估完複雜度後發現會TLE，實在苦思不知該如何做，直到有人雷了我說誰區間和在用BIT的，我才發現可以用維護前綴和的精神做這題，也就是說每個前綴變成存一棵treap，但是如果每一個前綴都重新插一遍所有東東到treap裡面會發現預處理變成$O(n^2 log(n))$，明顯會TLE，所以不妨用持久化的概念，也就是讓一部分是共用的，有修改到的部分再複製出來就好了，因為複製時最多只會動到一條跟到葉的路徑也就是最多$log(n)$個節點，因此複雜度還是$log(n)$，只是記憶體有點龐大而已。 #include <bits/stdc++.h> using namespace std; #define N 100000 struct treap{ treap *l, *r; int pri,val,size; treap(){l=r=nullptr;size=0;} treap(int x){l=r=nullptr;pri=rand();val=x;size=1;} }; inline int gSize(treap* x){return x?x->size:0;} inline void pull(treap* x){x->size=gSize(x->l)+1+gSize(x->r);} int arr[N+5], n; treap* root[N+5]; bool isOK(int,int,int); void split(treap*,int,treap*&,treap*&); treap* merge(treap*, treap*); int query(treap*,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0);...

題目連結: http://tioj.infor.org/problems/1208 不太確定該如何下手時，就先二分搜一陣吧，而且他還特別保證所有項的絕對值都不超過10,000，所以感覺二分搜有機會，那二分搜答案要怎麼驗證呢?其實對於一個數我們有能力可以知道有幾個連續和比他大，因為如果要看x是第幾大，則就是對於每個前綴和$a_i$我們都要找有多少個$a_j$使得$a_i - a_j > x$(其中$i>j$)，移項發現變成找有多少個$a_j+x #include <bits/stdc++.h> using namespace std; #define N 20000 class Treap{ private: struct __node{ __node* l; __node* r; int __pri,__size,__val; __node(){l=NULL;r=NULL;__pri=rand();__size=0;} __node(int x){l=NULL;r=NULL;__pri=rand();__size=1;__val=x;} ~__node(){if(l)delete l;if(r)delete r;l=NULL;r=NULL;} }; __node* __root; inline int __gSize(__node* __x){return (__x==NULL)?0:(__x->__size);} __node* __merge(__node* __x,__node* __y){ if(__x==NULL||__y==NULL)return __x?__x:__y; else if(__x->__pri > __y->__pri){ __x->r ...

題目連結: http://tioj.infor.org/problems/1382 原本用黑魔法過了這題，但覺得沒寫過平衡樹覺得還是該練練，所以就寫了個怪怪treap版本的(因為我會按照1,2,3,4...insert，所以不需要split)。這題的做法基本上就是每次查好你要砍那個，先輸出一下再刪掉就好，複雜度$O(n log n)$ #include <bits/stdc++.h> using namespace std; class tree{ private: struct node{ int size,val,pri; node* l; node* r; node* f; node(){f=NULL;l=NULL;r=NULL;size=0;pri=rand();} node(int x){f=NULL;l=NULL;r=NULL;size=1;val=x;pri=rand();} }; node* root; inline int gSize(node* x){return (x==NULL)?0:x->size;} node* merge(node* x, node* y){ if(x==NULL)return y; if(y==NULL)return x; bool xfa = (x->pri)>(y->pri); if(xfa){ if(y->val < x->val){ x->l=merge(x->l,y); x->l->f=x; ...