其實(shí)本質(zhì)上是優(yōu)化暴力。

網(wǎng)上都說(shuō)構(gòu)造的數(shù)據(jù)可以卡掉珂朵莉樹(shù)，是因?yàn)樵谛薷牡臅r(shí)候要遍歷set導(dǎo)致很容易卡掉，所以珂朵莉樹(shù)可能比較有局限性。

但是如果用來(lái)維護(hù)區(qū)間用于求交求并，復(fù)雜度是嚴(yán)格的log的，常數(shù)好像稍大，但是還是非常有用的。

放個(gè)板子：

1 #include<iostream> 2 #include<cstdio> 3 #include<set> 4 #define re register 5 #define co const 6 #define cor co re 7 #define INF 0x7ffffffffffffff 8 #define LL long long 9 const int L=1<<20|1; 10 char buffer[L],*S,*TT; 11 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++) 12 using namespace std; 13 int T,s,k,n; 14 LL a[500010],sum[500010]; 15 16 struct node 17 { 18 LL l,r; 19 mutable int v; 20 friend bool operator < (node a,node b) 21 {return a.l<b.l;} 22 }; 23 struct kdl_tree 24 { 25 set<node> s; 26 #define IT set<node>::iterator 27 IT spilit(cor LL pos) 28 { 29 IT it=s.lower_bound((node){pos,-1,0}); 30 if(it!=s.end()&&it->l==pos)return it; 31 it--; 32 LL L=it->l,R=it->r,v=it->v; 33 s.erase(it); 34 s.insert((node){L,pos-1,v}); 35 return s.insert((node){pos,R,v}).first; 36 } 37 void tp(cor LL l,cor LL r,cor int val) 38 { 39 IT ir=spilit(r+1),il=spilit(l); 40 s.erase(il,ir); 41 s.insert((node){l,r,val}); 42 } 43 }Tr; 44 inline int read(); 45 signed main() 46 { 47 // freopen("in.txt","r",stdin); 48 // freopen("1.out","w",stdout); 49 50 T=read(); 51 while(T--) 52 { 53 Tr.s.clear(); 54 s=read(),k=read(),n=read(); 55 sum[0]=0;for(re int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i]; 56 57 sum[n+1]=INF; 58 Tr.s.insert((node){-INF,0,1}); 59 for(re int i=1;i<=n;i+=2) 60 { 61 LL l=sum[i-1]+1,r=sum[i]+s-1; 62 LL tk=((l-1)/k+1)*k,bs=((l-1)/k+1); 63 if(tk<=r)Tr.tp( l-k*bs , tk-k*bs ,0),bs++; 64 Tr.tp( l-k*bs , r-k*bs , 0); 65 } 66 bool ok=0; 67 for(IT it=++Tr.s.begin();it!=Tr.s.end();it++) 68 if(it->l<=0&&it->r<=0) 69 if(it->v){ok=1;} 70 if(ok)puts("TAK"); 71 else puts("NIE"); 72 } 73 } 74 inline int read() 75 { 76 int s=0,f=1;char a=getchar(); 77 while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();} 78 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();} 79 return s*f; 80 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Al-Ca/p/11558698.html

總結(jié)

以上是生活随笔為你收集整理的模板—珂朵莉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。