1825.md (27602B)
1 Source: https://codeforces.com/blog/entry/116328 2 3 ## A. LuoTianyi and the Palindrome String 4 5 Consider the substring of $s$ from the second character to the last, or $s_2s_3\cdots s_n$. If it's not palindrome, then the answer must be $n-1$. What if it's palindrome? This implies that $s_2=s_n$, $s_3=s_{n-1}$, and so on. Meanwhile, the fact that $s$ is palindrome implies $s_1=s_n$, $s_2=s_{n-1}$, etc. So we get $s_1=s_n=s_2=s_{n-1}=\cdots$ or that all characters in $s$ is the same. In this situation, every subsequence of $s$ is palindrome of course, so the answer should be $-1$. 6 7 **Code** 8 9 ``` 10 #pragma GCC optimize(3,"Ofast","inline") 11 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") 12 #include <bits/stdc++.h> 13 #include <ext/pb_ds/assoc_container.hpp> 14 #include <ext/pb_ds/tree_policy.hpp> 15 //#define ll int 16 #define ft first 17 #define sd second 18 //#define endl '\n' 19 #define pb push_back 20 #define ll long long 21 #define pll pair<ll,ll> 22 #define no cout<<"NO"<<'\n' 23 #define no_ cout<<"No"<<'\n' 24 #define _no cout<<"no"<<'\n' 25 #define lowbit(a) ((a)&-(a)) 26 #define yes cout<<"YES"<<'\n' 27 #define yes_ cout<<"Yes"<<'\n' 28 #define _yes cout<<"yes"<<'\n' 29 #define ull unsigned long long 30 #define all(x) x.begin(),x.end() 31 #define nps fixed<<setprecision(10)<< 32 #define mem(a,k) memset(a,k,sizeof(a)) 33 #define debug(x) cout<<#x<<"="<<x<<endl 34 #define rep(i,a,b) for(ll i=(a);i<=(b);i++) 35 #define per(i,a,b) for(ll i=(a);i>=(b);i--) 36 const ll mod1=1e9+7; 37 const ll mod2=998244353; 38 const ll base=1610612741; 39 const ll INF=0x3f3f3f3f3f; 40 const ll inf=9223372036854775807; 41 const ll Z=mod2; 42 const ll mod=Z; 43 using namespace std; 44 int ddir[2][2]={{0,1},{1,0}}; 45 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; 46 int dir3[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}}; 47 struct custom_hash 48 { 49 static ull splitmix64(ull x){x+=0x9e3779b97f4a7c15;x=(x^(x>>30))*0xbf58476d1ce4e5b9;x=(x^(x>>27))*0x94d049bb133111eb;return x^(x>>31);} 50 size_t operator()(ull x)const{static const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);} 51 //unordered_map<ll,ll,custom_hash>mp; 52 }; 53 struct mint 54 { 55 ll x; 56 mint(ll y = 0){if(y < 0 || y >= mod) y = (y%mod+mod)%mod; x = y;} 57 mint(const mint &ope) {x = ope.x;} 58 mint operator-(){return mint(-x);} 59 mint operator+(const mint &ope){return mint(x) += ope;} 60 mint operator-(const mint &ope){return mint(x) -= ope;} 61 mint operator*(const mint &ope){return mint(x) *= ope;} 62 mint operator/(const mint &ope){return mint(x) /= ope;} 63 mint& operator+=(const mint &ope){x += ope.x; if(x >= mod) x -= mod; return *this;} 64 mint& operator-=(const mint &ope){x += mod - ope.x; if(x >= mod) x -= mod; return *this;} 65 mint& operator*=(const mint &ope){ll tmp = x; tmp *= ope.x, tmp %= mod; x = tmp; return *this;} 66 mint& operator/=(const mint &ope){ll n = mod-2; mint mul = ope;while(n){if(n & 1) *this *= mul; mul *= mul; n >>= 1;}return *this;} 67 mint inverse(){return mint(1) / *this;} 68 bool operator ==(const mint &ope){return x == ope.x;} 69 bool operator !=(const mint &ope){return x != ope.x;} 70 bool operator <(const mint &ope)const{return x < ope.x;} 71 }; 72 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 73 ll gcd(ll a,ll b){return __gcd(a,b);} 74 ll lcm(ll a,ll b){return a*b/__gcd(a,b);} 75 ll rnd(ll l,ll r){ll ans=uniform_int_distribution<ll>(l,r)(rng);return ans;} 76 ll qpow(ll a,ll b){ll res=1;while(b>0){if(b&1)res=res*a;a=a*a;b>>=1;}return res;} 77 ll qpow(ll a,ll b,ll m){a%=m;ll res=1;while(b>0){if(b&1)res=res*a%m;a=a*a%m;b>>=1;}return res;} 78 double psqrt(double x,double y,double xx,double yy){double res=((x-xx)*(x-xx)+(y-yy)*(y-yy));return res;} 79 double ssqrt(double x,double y,double xx,double yy){double res=sqrt(psqrt(x,y,xx,yy));return res;} 80 ll INV(ll x){return qpow(x,Z-2,Z);} 81 void cominit(ll fac[],ll inv[]){fac[0]=1;rep(i,1,1000000)fac[i]=fac[i-1]*i%Z; 82 inv[1000000]=INV(fac[1000000]);per(i,1000000-1,0)inv[i]=inv[i+1]*(i+1)%Z;} 83 ll t,n,m,k,tt,tp,res,sum,ans,cnt; 84 const ll N=1e6+5; 85 ll a[N],b[N]; 86 int main() 87 { 88 ios::sync_with_stdio(false); 89 cin.tie(nullptr),cout.tie(nullptr); 90 //IO 91 cin>>t; 92 while(t--) 93 { 94 string s; 95 cin>>s; 96 auto check=[&]() 97 { 98 for(int i=0;i<s.size()/2;++i)if(s[i]!=s[s.size()-i-1])return 0; 99 return 1; 100 }; 101 if(!check())ans=s.size(); 102 else if(s.size()>1) 103 { 104 s.pop_back(); 105 if(!check())ans=s.size(); 106 else ans=-1; 107 } 108 else ans=-1; 109 cout<<ans<<"\n"; 110 } 111 } 112 ``` 113 114 ## B. LuoTianyi and the Grid 115 116 Assume that $n \gt m$. Greedily thinking, we want the maximum possible $a$ to appear as the maximum value of as many subtables as possible, meanwhile, we also want the minimum possible $a$ to appear as the minimum value of as many subtables as possible. This gives us two choices: making the upper-left square the minimum or the maximum. It's symmetrical so we'll only consider the minimum situation. 117 118 Now all the subtables have the same minimum value, we want to maximize the number of subtables where the maximum $a$ appears as the maximum value. Placing it at $(1,2)$ and $(2,1)$ makes the number $n(m-1),m(n-1)$ each, because $n \gt m$, we have $m(n-1) \gt n(m-1)$, so we place the largest $a$ at $(2,1)$ and the second largest at $(1,2)$, the answer for this case is $m(n-1)\times \max+m\times \text{second max}-mn\times\min$. 119 120 **Code** 121 122 ``` 123 #include<bits/stdc++.h> 124 #define ll long long 125 using namespace std; 126 const int mxn=2e5+5; 127 ll a[mxn]; 128 inline void solve(){ 129 ll n,m; 130 cin>>n>>m; 131 for(int i=1;i<=n*m;++i)cin>>a[i]; 132 sort(a+1,a+n*m+1); 133 if(n>m)swap(n,m); 134 if(n==1)cout<<(m-1)*(a[n*m]-a[1])<<'\n'; 135 else{ 136 ll ans1=(n*m-1)*(a[n*m])-a[1]*(n*(m-1))-a[2]*(n-1); 137 ll ans2=a[n*m]*(n*(m-1))+a[n*m-1]*(n-1)-a[1]*(n*m-1); 138 cout<<max(ans1,ans2)<<'\n'; 139 } 140 } 141 int main(){ 142 ios_base::sync_with_stdio(false); 143 cin.tie(0),cout.tie(0); 144 int T;cin>>T; 145 for(;T--;)solve(); 146 return 0; 147 } 148 ``` 149 150 ## C. LuoTianyi and the Show 151 152 First we can notice that, if someone with a specific favourite seat(i.e. not $-1$ nor $-2$) has got his seat taken by a $-1$ guy or a $-2$ guy, it's better to let the first man go first, and the $-1$ or $-2$ one go after him. 153 154 Now, we know it's better to make those with a favourite seat go in first. After they have seated, now we consider filling the space between them with $-1$ and $-2$. It's easy to notice that we can find two non-overlapping prefix and suffix, and fill the blank seats in the prefix with $-1$, and the blanks in the suffix with $-2$. We now only need to find the answer greedily for each division point between the prefix and the suffix. 155 156 The time complexity is $O(n)$. 157 158 **Code** 159 160 ``` 161 // Problem: C. LuoTianyi and the Theater 162 // Contest: Codeforces - test vocaloid cf round 163 // URL: https://codeforces.com/gym/394370/problem/C 164 // Memory Limit: 256 MB 165 // Time Limit: 1000 ms 166 // 167 // Powered by CP Editor (https://cpeditor.org) 168 169 //By: OIer rui_er 170 #include <bits/stdc++.h> 171 #define rep(x,y,z) for(int x=(y);x<=(z);x++) 172 #define per(x,y,z) for(int x=(y);x>=(z);x--) 173 #define debug(format...) fprintf(stderr, format) 174 #define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false) 175 using namespace std; 176 typedef long long ll; 177 const int N = 2e5+5; 178 179 int T, n, m, a[N], buc[N]; 180 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;} 181 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} 182 183 int main() { 184 for(scanf("%d", &T); T; T--) { 185 scanf("%d%d", &n, &m); 186 rep(i, 1, n) scanf("%d", &a[i]); 187 int cntL = 0, cntR = 0; 188 rep(i, 1, n) { 189 if(a[i] == -1) ++cntL; 190 else if(a[i] == -2) ++cntR; 191 else ++buc[a[i]]; 192 } 193 int nowL = 0, nowR = 0, vis = 0; 194 rep(i, 1, m) { 195 if(buc[i]) ++vis; 196 else ++nowR; 197 } 198 int ans = max(cntL, cntR) + vis; 199 rep(i, 1, m) { 200 // printf("%d : %d %d; %d %d; %d\n", i, cntL, nowL, cntR, nowR, vis); 201 if(buc[i]) chkmax(ans, min(cntL, nowL) + min(cntR, nowR) + vis); 202 else ++nowL, --nowR; 203 // printf(" -> %d\n", ans); 204 } 205 chkmin(ans, m); 206 printf("%d\n", ans); 207 rep(i, 1, m) buc[i] = 0; 208 } 209 return 0; 210 } 211 ``` 212 213 ## D. LuoTianyi and the Floating Islands 214 215 Call a node special if there is a person in it. 216 217 When $k$ is odd, we find that there is only one node satisfying the conditions. 218 219 $\bf{Proof}.$ Assume distinct node $x$ and node $y$ are good nodes. Let $x$ be the root of the tree. Define $s_i$ as the number of special nodes in subtree $i$. Think about the process we move from $x$ to $y$. If we try to move the chosen node from its father to $i$, the variation of cost is $k-2s_i$. When move from $x$ to its son $i$ which $s_i$ is maximal, $k-2s_i\geq 0$ is held (Otherwise, $x$ isn't a good node). And we can get $k-2s_i \gt 0$ further because $k$ is odd and $2s_i$ is even. Since $\min_{1\leq j\leq n}{k-2s_j}=k-2s_i$, we find $k-2s_j \gt 0$ for all $j$. So $y$ can't be good node. 220 221 Then think about the situation that $k$ is even. Choose a node as root arbitrarily. With the same method, we find that good nodes satisfy $2s_i=k$. It's also sufficient. Define $p_i$ as the possibility that $s_i=\frac{k}{2}$, then the answer is $1+\sum_{i=1}^{n}p_i$. 222 223 Define $S_i$ as the size of subtree $i$. When $s_i=\frac{k}{2}$, there are $\frac{k}{2}$ special nodes in subtree $i$ and $\frac{k}{2}$ in the other part. The number of ways to place special nodes is $\binom{n}{k}$, and $\binom{S_i}{\frac{k}{2}}\binom{n-S_i}{\frac{k}{2}}$ of them satisfying the condition. So $p_i=\dfrac{\binom{S_i}{\frac{k}{2}}\binom{n-S_i}{\frac{k}{2}}}{\binom{n}{k}}$. 224 225 So we can solve the problem in $O(n)$. 226 227 **Code** 228 229 ``` 230 //Was yea ra,rra yea ra synk sphilar yor en me exec hymme METAFALICA waath! 231 #pragma GCC optimize("Ofast") 232 #pragma GCC optimize("unroll-loops") 233 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") 234 #include<bits/stdc++.h> 235 using namespace std; 236 #define rg register 237 #define ll long long 238 #define ull unsigned ll 239 #define lowbit(x) (x&(-x)) 240 #define djq 1000000007 241 const double eps=1e-10; 242 const short sint=0x3f3f; 243 const int inf=0x3f3f3f3f; 244 const ll linf=0x3f3f3f3f3f3f3f3f; 245 const double alpha=0.73; 246 const double PI=acos(-1); 247 inline void file(){ 248 freopen("1.in","r",stdin); 249 freopen("1.out","w",stdout); 250 } 251 char buf[1<<21],*p1=buf,*p2=buf; 252 inline int getc(){ 253 return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<20)+5,stdin),p1==p2)?EOF:*p1++; 254 } 255 //#define getc getchar 256 inline ll read(){ 257 rg ll ret=0,f=0;char ch=getc(); 258 while(!isdigit(ch)){if(ch==EOF)exit(0);if(ch=='-')f=1;ch=getc();} 259 while(isdigit(ch)){ret=ret*10+ch-48;ch=getc();} 260 return f?-ret:ret; 261 } 262 inline void rdstr(char* s){ 263 char ch=getc(); 264 while(ch<33||ch>126) ch=getc(); 265 while(ch>=33&&ch<=126) (*s++)=ch,ch=getc(); 266 } 267 #define ep emplace 268 #define epb emplace_back 269 #define all(x) (x).begin(),(x).end() 270 #define fi first 271 #define se second 272 #define it iterator 273 #define mkp make_pair 274 #define naive return 0*puts("Yes") 275 #define angry return 0*puts("No") 276 #define fls fflush(stdout) 277 #define rep(i,a) for(rg int i=1;i<=a;++i) 278 #define per(i,a) for(rg int i=a;i;--i) 279 #define rep0(i,a) for(rg int i=0;i<=a;++i) 280 #define per0(i,a) for(rg int i=a;~i;--i) 281 #define szf sizeof 282 typedef vector<int> vec; 283 typedef pair<int,int> pii; 284 struct point{ int x,y; point(int x=0,int y=0):x(x),y(y) {} inline bool operator<(const point& T)const{ return x^T.x?x<T.x:y<T.y; }; }; 285 inline int ksm(int base,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*base%djq;base=1ll*base*base%djq,p>>=1;}return ret;} 286 inline void pls(int& x,const int k){ x=(x+k>=djq?x+k-djq:x+k); } 287 inline int add(const int a,const int b){ return a+b>=djq?a+b-djq:a+b; } 288 inline void sub(int& x,const int k){ x=(x-k<0?x-k+djq:x-k); } 289 inline int inc(const int a,const int b){ return a<b?a-b+djq:a-b; } 290 inline void ckmn(int& x,const int k){ x=(k<x?k:x); } 291 inline void ckmx(int& x,const int k){ x=(k>x?k:x); } 292 293 const int lim=2e5; 294 int fac[200005],ifac[200005]; 295 inline int C(int n,int m){ return (m<=n&&m>=0&&n>=0)?1ll*fac[n]*ifac[m]%djq*ifac[n-m]%djq:0; } 296 void initC(){ 297 fac[0]=ifac[0]=1; 298 rep(i,lim) fac[i]=1ll*fac[i-1]*i%djq; 299 ifac[lim]=ksm(fac[lim],djq-2); 300 per(i,lim-1) ifac[i]=1ll*ifac[i+1]*(i+1)%djq; 301 } 302 int n,k,u,v,sz[200005]; 303 vec e[200005]; 304 void dfs(int x,int fa){ 305 sz[x]=1; 306 for(int y:e[x]) if(y^fa) dfs(y,x),sz[x]+=sz[y]; 307 } 308 signed main(){ 309 //file(); 310 initC(); 311 n=read(),k=read(); 312 rep(i,n-1) u=read(),v=read(),e[u].epb(v),e[v].epb(u); 313 dfs(1,0); 314 if(k&1) return 0*puts("1"); 315 else{ 316 int ans=0; 317 for(rg int i=2;i<=n;++i) pls(ans,1ll*C(sz[i],k/2)*C(n-sz[i],k/2)%djq); 318 ans=1ll*ans*ksm(C(n,k),djq-2)%djq; 319 pls(ans,1); 320 printf("%d\n",ans); 321 } 322 return 0; 323 } 324 ``` 325 326 ## E. LuoTianyi and XOR-Tree 327 328 Hint: Consider a brute force dynamic programming solution and try to optimize it. 329 330 Denote the minimum number of operations needed to make every path from a leaf inside the subtree of $u$ to the root have the xor value of $w$ as $f_{u,w}$. Observe that for every $u$, there are only $2$ possible different values for $f_{u,w}$. This is because if $f_{u,w_1}-f_{u,w_2} \gt 1$, we can use an operation of xor-ing $a_u$ with $w_1 \ \text{xor} \ w_2$ to make all the xor values from $w_2$ to $w_1$, which takes $f_{u,w_2}+1$ steps instead of $f_{u,w_1}$. 331 332 Now we only need to calculate $\text{minn}_u=\min f_{u,w}$, and the set $S_u$ of $w$ that makes $f_{u,w}$ minimum. We have $\text{minn}_v=0$ and $S_v={\text{the xor value from root to v}}$ for leaf $v$. It's trivial to calculate $\text{minn}_u$. 333 334 Note that $S_u$ contains of the numbers appearing the most times in the sets of $u$'s son. We can maintain $S_u$ using a map and merging it heuristically. Consider when merging sets into a new set $S'$. If every element of $S'$ appears only once in the original sets, then we keep $S'$ as the result, otherwise, brute force the whole set $S'$ and find the elements appearing the most times. For the second situation, every element's count of appearance is at least halved(those appearing once have $0$ and others have $1$ afterwards), so the number of brute force checking operations is $O(n\log n)$. 335 336 The final time complexity is $O(n\log^2 n)$. 337 338 **Code** 339 340 ``` 341 #include<iostream> 342 #include<cstdio> 343 #include<vector> 344 #include<set> 345 #include<algorithm> 346 #include<map> 347 using namespace std; 348 int n,a[100005]; 349 vector<int> e[100005]; 350 set<int> s[100005],stmp; 351 int ans=0,sid[100005],stp=0; 352 bool cmp(int x,int y) 353 { 354 return (int)s[sid[x]].size()>(int)s[sid[y]].size(); 355 } 356 void set_xor(int x,int y) 357 { 358 stmp.clear(); 359 set<int>::iterator it=s[x].begin(); 360 while(it!=s[x].end()) 361 stmp.insert(y^(*(it++))); 362 s[x]=stmp; 363 return ; 364 } 365 void dfs(int u,int f) 366 { 367 vector<int> v; 368 for(int i=0;i<(int)e[u].size();i++) 369 if(e[u][i]!=f) 370 { 371 dfs(e[u][i],u); 372 v.push_back(e[u][i]); 373 } 374 if((int)v.size()==0) 375 { 376 sid[u]=(++stp); 377 s[sid[u]].insert(0); 378 return ; 379 } 380 sort(v.begin(),v.end(),cmp); 381 int hv_tg=a[v[0]]; 382 a[v[0]]=0; 383 a[u]^=hv_tg; 384 bool flg=false; 385 set<int> setchk; 386 for(int i=1;i<(int)v.size();i++) 387 { 388 int x=v[i]; 389 set_xor(sid[x],a[x]^hv_tg); 390 set<int>::iterator it=s[sid[x]].begin(); 391 while(it!=s[sid[x]].end()) 392 { 393 int val=(*it); it++; 394 if(s[sid[v[0]]].find(val)!=s[sid[v[0]]].end()) 395 flg=true; 396 if(setchk.find(val)!=setchk.end()) 397 flg=true; 398 setchk.insert(val); 399 } 400 } 401 if(flg==false) 402 { 403 //cout<<"Node "<<u<<" "<<(int)v.size()-1<<endl; 404 ans+=(int)v.size()-1; 405 for(int i=1;i<(int)v.size();i++) 406 { 407 int x=v[i]; 408 set<int>::iterator it=s[sid[x]].begin(); 409 while(it!=s[sid[x]].end()) 410 s[sid[v[0]]].insert(*(it++)); 411 } 412 sid[u]=sid[v[0]]; 413 return ; 414 } 415 map<int,int> h; 416 for(int i=0;i<(int)v.size();i++) 417 { 418 int x=v[i]; 419 set<int>::iterator it=s[sid[x]].begin(); 420 while(it!=s[sid[x]].end()) 421 h[*(it++)]++; 422 } 423 sid[u]=(++stp); 424 int mx_app=0; 425 map<int,int>::iterator it=h.begin(); 426 while(it!=h.end()) 427 { 428 pair<int,int> p=(*it); 429 if(p.second>mx_app) 430 { 431 mx_app=p.second; 432 s[sid[u]].clear(); 433 } 434 if(p.second==mx_app) 435 s[sid[u]].insert(p.first); 436 it++; 437 } 438 ans+=(int)v.size()-mx_app; 439 return ; 440 } 441 int main() 442 { 443 scanf("%d",&n); 444 for(int i=1;i<=n;i++) 445 scanf("%d",&a[i]); 446 for(int i=1;i<n;i++) 447 { 448 int u,v; 449 scanf("%d%d",&u,&v); 450 e[u].push_back(v); 451 e[v].push_back(u); 452 } 453 dfs(1,0); 454 set_xor(sid[1],a[1]); 455 if(s[sid[1]].find(0)==s[sid[1]].end()) 456 ans++; 457 printf("%d\n",ans); 458 return 0; 459 } 460 ``` 461 462 ## F. LuoTianyi and the Function 463 464 Consider an alternative method of calculating $g$. Notice that $g(i,j)$ is the minimum of the last appearing position of all colors(let's call different values of $a_x$ colors for short) in the interval $[i,j]$. 465 466 Consider the sequence from $a_n$ to $a_1$. Adding $a_i$ to the front of the sequence only affects the values $g(i,x)(i\leq x \lt \text{nxt}_i)$, where $\text{nxt}_i$ is the next position after $i$ having the same $a$ value as it. Or it's to say to modify $g$ values in the submatrix of $[(1,i),(i,\text{nxt}_i-1)]$ to $i$, which can be done in $O(n\log^2 n)$, but it's not fast enough. 467 468 Because the queries happen after all modifications take place, you can store the queries offline, and calculate a submatrix using $4$ queries of submatrixes having $(1,1)$ as the upper-left corner. Now we need to maintain a data structure that can: 1. set all values in an interval as a same value $x$, 2. query the history sum(sum of values on all previous editions). We can maintain the segments of adjacent positions with the same values, and turn the modification into 'range add' for a segment. 469 470 An operation makes at most $O(1)$ new segments, and now there's only $O(n)$ range add modifications and $O(m)$ range history sum queries, now the problem can be solved in $O(n\log n)$ time complexity with segment tree. 471 472 **Code** 473 474 ``` 475 #include<bits/stdc++.h> 476 using namespace std; 477 #define N 1000005 478 #define L long long 479 int n,m,stt,a[N],nxt[N],siz[N],top,ll[N],rr[N],xx[N],yy[N]; 480 L out[N]; 481 struct ds{ 482 L t[2][N],ta; 483 inline void add(int op,int x,L v){while(x<=n) t[op][x]+=v,x+=(x&-x);} 484 inline L ask(int op,int x){ta=0;while(x) ta+=t[op][x],x^=(x&-x);return ta;} 485 void Add(int l,int r,L v){add(0,l,v),add(0,r+1,-v),add(1,l,v*(l-1)),add(1,r+1,-v*r);} 486 L Ask(int l,int r){return r*ask(0,r)-(l-1)*ask(0,l-1)-ask(1,r)+ask(1,l-1);} 487 } b1,b2; 488 struct node{int l,r,v;} st[N]; 489 struct query{int id,op;} pl[2*N]; 490 query *v[N]; 491 signed main(){ 492 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 493 cin>>n>>m; 494 for(int i=1;i<=n;++i) cin>>a[i],siz[a[i]]=n+1; 495 for(int i=n;i>=1;--i) nxt[i]=siz[a[i]],siz[a[i]]=i; 496 memset(siz,0,sizeof siz); 497 for(int i=1;i<=m;++i){ 498 cin>>ll[i]>>rr[i]>>xx[i]>>yy[i]; 499 siz[ll[i]]++,siz[rr[i]+1]++; 500 } 501 for(int i=1;i<=n+1;++i) v[i]=pl+top,top+=siz[i]; 502 memset(siz,0,sizeof siz); 503 for(int i=1;i<=m;++i) v[ll[i]][siz[ll[i]]++]=(query){i,1},v[rr[i]+1][siz[rr[i]+1]++]=(query){i,-1}; 504 for(int i=n,l,r;i>=1;--i){ 505 l=i,r=nxt[i]-1; 506 while(stt&&r>=st[stt].r){ 507 node &nw=st[stt]; 508 b1.Add(nw.l,nw.r,1ll*-i*nw.v),b2.Add(nw.l,nw.r,-nw.v); 509 stt--; 510 } 511 if(stt&&st[stt].l<=r){ 512 node &nw=st[stt]; 513 b1.Add(nw.l,r,1ll*-i*nw.v),b2.Add(nw.l,r,-nw.v); 514 nw.l=r+1; 515 } 516 st[++stt]=(node){l,r,i}; 517 b1.Add(l,r,1ll*i*i),b2.Add(l,r,i); 518 for(int j=0;j<siz[i];++j) out[v[i][j].id]+=1ll*v[i][j].op*(b1.Ask(xx[v[i][j].id],yy[v[i][j].id])-1ll*(i-1)*b2.Ask(xx[v[i][j].id],yy[v[i][j].id])); 519 } 520 for(int i=1;i<=m;++i) cout<<out[i]<<'\n'; 521 } 522 ``` 523 524 ## G. LuoTianyi and Cartridge 525 526 Consider finding the maximum value of $B+D$ for every $\min(A,C)$. Denote $\min(A,C)$ as $x$. We call a vertex $u$ satisfying $a_u\geq x$ or an edge satisfying $c_e\geq x$ **optional**. Denote as $V$ the optional vertex set and as $E_0$ the optional edge set. 527 528 Firstly, if all optional vertices are on the same side of an edge, this edge mustn't be chosen. Delete these edges from $E_0$ and we get the edge set $E$. Formally, an edge $e$ is in $E$ if and only if $c_e\geq x$ and there exists $u,v$ so that $e$ is on the path between them. 529 530 $\bf{Lemma.}$ **There exists an optimal $T_{\text{ans}}=(V_\text{ans},E_\text{ans})$ that either $V=V_\text{ans}$ or $E=E_\text{ans}$.** 531 532 $\bf{Proof.}$ Assume an optimal $T'=(V',E')$ with $V'\neq V,E'\neq E$. Choose an edge $e$ that is in $E$ but not in $E'$. Because $V'\neq V$, there must exist two vertices $u,v$ on different sides of edge $e$ and $u\in V',v\notin V'$. Consider adding the edge $e$ and the vertex $v$ into our chosen tree, the resulting graph is obviously a tree. Note that $b_v,d_e\geq 0$, so the resulting choice is no worse than $T'$. 533 534 When we delete the edges in $E$ from the original tree, we get some connected components. Shrink one component into a single vertex to get $V'$, and then for all edges $(u,v)\in E$, connect $u$'s and $v$'s component together in the new graph and get $E'$. Obviously, the new graph $T'=(V',E')$ is a tree. 535 536 For any leaf vertex $u'$ on the new tree $T'$, there must exist a vertex $u$ in the component $u'$ that is chosen, otherwise the edge connecting to $u'$, let's say, $e'$ is not chosen either. Adding $u$ and $e'$ into our answer tree achieves a better answer. 537 538 Assume that now we have chosen a vertex $u$ for every leaf $u'$, denote the set of chosen vertices as $V_x$. Consider an arbitary choice of vertex for components $V_c$ and edge choice $E_c$ satisfying $V_x\subseteq V_c\subseteq V,E_c\subseteq E,|V_c|-1=|E_c|$. It's easy to prove that the choice is a legal answer, given the fact that every $e\in E_c$ has at least one leaf component on each side and every leaf component contains a chosen vertex. 539 540 Reconsider the lemma, and we can get a solution for a fixed $x$: 541 542 1. Find $V,E$. Calculate the components and get $V',E'$. 543 2. Find the vertex with the maximum $b$ in every leaf-component in $V'$ and get $V_x$. 544 3. Let $m$ be $\min(|V|,|E|+1)$, and $m'$ be $|V_x|$. Choose the vertices in $V\setminus V_x$ with the first $m-m'$ largest $b$, and the edges in $E$ with the first $m-1$ largest $d$ and get the answer. 545 546 Consider the process when $x$ gets larger, the sets $V,E$ get smaller and smaller while the components merge into each other. We use segment trees to maintain the $b$ value of the vertices and the $d$ value of the edges, when merging two components, we simply merge the two segment trees. 547 548 The final time complexity is $O(n\log n)$. 549 550 **Code** 551 552 ``` 553 #include<bits/stdc++.h> 554 using namespace std; 555 typedef long long ll; 556 typedef pair<int,int> pii; 557 const int MAXN = 2e5 + 5; 558 const int inf = 0x3f3f3f3f; 559 const ll linf = 0x3f3f3f3f3f3f3f3f; 560 561 struct Segment_Tree 562 { 563 static const int N = 1<<18, SIZ = N * 2 + 5; 564 pii mx[SIZ]; 565 Segment_Tree(void){ clear();} 566 void clear(void) 567 { 568 for(int i=0; i<N; ++i) 569 mx[N+i] = {-inf, i}; 570 for(int i=N-1; i>=1; --i) 571 mx[i] = max(mx[i<<1], mx[i<<1|1]); 572 } 573 void set(int i,int k) 574 { 575 i += N; 576 mx[i].first = k; 577 while((i >>= 1) != 0) 578 mx[i] = max(mx[i<<1], mx[i<<1|1]); 579 } 580 pii query(int l,int r) 581 { 582 pii res = {-inf, -inf}; 583 for(l+=N-1, r+=N+1; l^r^1; l>>=1, r>>=1) 584 { 585 if(~l&1) res = max(res, mx[l^1]); 586 if( r&1) res = max(res, mx[r^1]); 587 } 588 return res; 589 } 590 }tree; 591 592 struct DS 593 { 594 multiset<int> l,r; 595 ll sum; 596 DS(void){ clear();} 597 void clear(void){ l.clear(); r.clear(); sum = 0;} 598 void insert(int x) 599 { 600 if(!r.size() || x < *r.begin()) l.emplace(x); 601 else r.emplace(x), sum += x; 602 } 603 void erase(int x) 604 { 605 if(l.find(x) != l.end()) 606 l.erase(l.find(x)); 607 else 608 r.erase(r.find(x)), sum -= x; 609 } 610 int size(void) const 611 { 612 return (int)l.size() + (int)r.size(); 613 } 614 ll query(int k) 615 { 616 while((int)r.size() > k) 617 { 618 int x = *r.begin(); r.erase(r.begin()); sum -= x; 619 l.emplace(x); 620 } 621 while((int)r.size() < k && l.size()) 622 { 623 int x = *l.rbegin(); l.erase(prev(l.end())); 624 r.emplace(x); sum += x; 625 } 626 return sum; 627 } 628 }; 629 630 array<int,2> p[MAXN]; 631 array<int,4> es[MAXN]; 632 633 vector<pii> g[MAXN]; 634 635 int anc[MAXN], ancid[MAXN]; 636 void dfs_tree(int u,int fa) 637 { 638 for(auto it: g[u]) if(it.first != fa) 639 { 640 int v = it.first; 641 anc[v] = u; 642 ancid[v] = it.second; 643 dfs_tree(v,u); 644 } 645 } 646 647 int dfnl[MAXN], dfnr[MAXN], seq[MAXN], curdfn; 648 void dfs_dfn(int u,int fa) 649 { 650 dfnl[u] = ++curdfn; seq[curdfn] = u; 651 for(auto it: g[u]) if(it.first != fa) 652 dfs_dfn(it.first, u); 653 dfnr[u] = curdfn; 654 } 655 656 int main(void) 657 { 658 int n; 659 scanf("%d",&n); 660 for(int i=1; i<=n; ++i) 661 scanf("%d",&p[i][0]); 662 for(int i=1; i<=n; ++i) 663 scanf("%d",&p[i][1]); 664 for(int i=1; i<n; ++i) 665 for(int &t: es[i]) 666 scanf("%d",&t); 667 668 vector<pii> vec; 669 for(int i=1; i<=n; ++i) 670 vec.emplace_back(p[i][0], i << 1 | 0); 671 for(int i=1; i<n; ++i) 672 { 673 vec.emplace_back(es[i][2], i << 1 | 1); 674 675 int u = es[i][0], v = es[i][1]; 676 g[u].emplace_back(v,i); 677 g[v].emplace_back(u,i); 678 } 679 680 sort(vec.begin(), vec.end()); 681 reverse(vec.begin(), vec.end()); 682 683 ll ans = 0; 684 vector<pii> eff; 685 686 int cntp = 0, cnte = 0; 687 ll sump = 0, sume = 0; 688 DS ds; 689 690 // Part 1 691 { 692 int rt; 693 { 694 int i = 0; 695 while(vec[i].second % 2 == 1) ++i; 696 rt = vec[i].second >> 1; 697 } 698 699 anc[rt] = 0; ancid[rt] = 0; 700 dfs_tree(rt,0); 701 702 static int tage[MAXN]; 703 704 auto insert_edge = [&] (int i,int curval) 705 { 706 if(tage[i] != 3) return; 707 // printf("insert_edge %d\n",i); 708 eff.emplace_back(curval, i << 1 | 1); 709 ds.insert(es[i][3]); 710 cnte += 1; 711 sume += es[i][3]; 712 }; 713 auto insert_node = [&] (int u,int curval) 714 { 715 // printf("insert_node %d\n",u); 716 eff.emplace_back(curval, u << 1 | 0); 717 cntp += 1; 718 sump += p[u][1]; 719 720 while(u != rt && (tage[ancid[u]] & 1) == 0) 721 { 722 tage[ancid[u]] |= 1; 723 insert_edge(ancid[u], curval); 724 u = anc[u]; 725 } 726 }; 727 728 for(auto t: vec) 729 { 730 int i = t.second >> 1, type = t.second & 1; 731 if(type == 0) 732 { 733 insert_node(i, t.first); 734 } 735 else 736 { 737 tage[i] |= 2; 738 insert_edge(i, t.first); 739 } 740 741 if(cntp >= 1 && cnte >= cntp - 1) 742 { 743 ll cur = sump + ds.query(cntp - 1); 744 ans = max(ans, t.first * cur); 745 } 746 } 747 } 748 749 // Part 2 750 { 751 int rtid, rt1, rt2; 752 { 753 int i = 0; 754 while(eff[i].second % 2 == 0) ++i; 755 rtid = eff[i].second >> 1; 756 rt1 = es[rtid][0]; 757 rt2 = es[rtid][1]; 758 } 759 760 dfs_dfn(rt1,rt2); 761 dfs_dfn(rt2,rt1); 762 763 cntp = cnte = sump = sume = 0; 764 ds.clear(); 765 map<int,pii> seg; 766 ll has = 0; 767 768 auto insert_seg = [&] (int l,int r) 769 { 770 auto it = seg.lower_bound(l); 771 if(it != seg.end() && it -> second.first <= r) return; 772 if(it != seg.begin()) 773 { 774 --it; 775 if(it -> second.first >= l) 776 { 777 int j = it -> second.second; 778 seg.erase(it); 779 ds.insert(p[j][1]); 780 tree.set(dfnl[j], p[j][1]); 781 has -= p[j][1]; 782 } 783 } 784 785 assert(tree.query(l,r).second != -inf); 786 int j = seq[ tree.query(l,r).second ]; 787 ds.erase(p[j][1]); 788 tree.set(dfnl[j], -inf); 789 has += p[j][1]; 790 seg[l] = {r, j}; 791 }; 792 793 for(auto t: eff) 794 { 795 int i = t.second >> 1, type = t.second & 1; 796 if(type == 0) 797 { 798 bool flag = [&] (void) -> bool 799 { 800 auto it = seg.upper_bound(dfnl[i]); 801 if(it == seg.begin()) return 0; 802 803 --it; 804 if(it -> second.first < dfnl[i]) return 0; 805 806 int j = it -> second.second; 807 if(p[j][1] >= p[i][1]) return 0; 808 809 ds.insert(p[j][1]); 810 tree.set(dfnl[j], p[j][1]); 811 it -> second.second = i; 812 has = has - p[j][1] + p[i][1]; 813 return 1; 814 }(); 815 816 if(!flag) 817 { 818 ds.insert(p[i][1]); 819 tree.set(dfnl[i], p[i][1]); 820 } 821 822 ++cntp; sump += p[i][1]; 823 } 824 else 825 { 826 if(i == rtid) 827 { 828 insert_seg(dfnl[rt1], dfnr[rt1]); 829 insert_seg(dfnl[rt2], dfnr[rt2]); 830 } 831 else 832 { 833 int u = es[i][0], v = es[i][1]; 834 if(dfnl[u] < dfnl[v]) swap(u, v); 835 insert_seg(dfnl[u], dfnr[u]); 836 } 837 838 ++cnte; sume += es[i][3]; 839 } 840 841 if(cntp >= cnte + 1) 842 { 843 ll cur = sume + has + ds.query(cnte + 1 - (int)seg.size()); 844 ans = max(ans, t.first * cur); 845 } 846 } 847 } 848 849 printf("%lld\n",ans); 850 return 0; 851 } 852 ```