codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```