#include <bits/stdc++.h>
using namespace std;


int main() {

    #ifdef ABHISHEK_SRIVASTAVA
        freopen("Input.txt", "r", stdin);
        freopen("Output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, k, curr = 1, cost = 0;
        cin >> n >> k;
        bool change = 0;
        while (k > 0) {
            k--;
            cost += curr;
            if (change)
                curr++;
            change = 1 - change;            
        }
        cout << cost << '\n';
    }

    return 0;

}

• For $$$k=0$$$, we don't color any cell;

• For $$$k=1$$$, we color cell $$$(1,1)$$$;

• For $$$k=2$$$, we color cells $$$(1,1),(n,n)$$$;

• For $$$k=3$$$, we color cells $$$(1,1),(n,n),(1,2),(2,1)$$$;

• For $$$k=4$$$, we color cells $$$(1,1),(n,n),(1,2),(2,1),(n-1,n),(n,n-1)$$$;

• $$$\ldots$$$

#include<bits/stdc++.h>
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> v[200010];
int a[200010]; 
void solve(){
	int n,m,po=-1,ans=1,b;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
		v[a[i]].clear();
	}
	for(int i=0;i<m;i++){
		cin>>b;
		v[b].eb(i);
	}
	for(int i=0;i<n;i++){
		if(!v[a[i]].size()){
			cout<<"-1\n";
			return;
		}
		int p=upper_bound(v[a[i]].begin(),v[a[i]].end(),po)-v[a[i]].begin();
		if(p==v[a[i]].size()){
			po=v[a[i]][0];
			ans++;
		}
		else po=v[a[i]][p];
	}
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

We use vectors $$$pos_i$$$ to represent all positions (in increasing order) of elements with value $$$i$$$ in array $$$b$$$.

Let's start from $$$a_1$$$. We can greedily choose the smallest $$$p$$$ such that $$$b_p = a_1$$$, and match $$$a_1$$$ with $$$b_p$$$.

Assume we have matched $$$a_{1,2, \dots ,i}$$$, and $$$p$$$ satisfies $$$a_i = b_p$$$.

Next, we want to match $$$a_{i+1}$$$. Again, we can greedily choose $$$pos_{a_{i+1}}.\text{upper_bound}(p)$$$. If there is no such $$$p$$$, then $$$ans++$$$, and $$$p = pos_{a_{i+1}}.\text{head()}$$$.

The case with no solution can be easily determined using the above method.

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int mod=998244353;
//give sin(),cos() radian, and asin(),acos() gives you radian
void solve(){
	ll n,ans=1,sum,p;
	cin>>n;
	if(n%2){
		sum=8;
		p=3;
	}
	else{
		sum=4;
		p=2;
	}
	for(ll i=n/2;i>0;i--){
		ans*=sum;
		ans%=mod;
		sum--;
		ans*=sum;
		ans%=mod;
		sum--;
		sum+=((2*p)+2)*2;
		sum%=mod;
		p+=2;
	}
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

Consider $$$m = 1, 2, \ldots, \left\lfloor \frac{n}{2} \right\rfloor$$$(Here area $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ refers to the rectangular region with ($$$x_1$$$,$$$y_1$$$) as the top-left corner and ($$$x_2$$$,$$$y_2$$$) as the bottom-right corner ).

• $$$1$$$ can be put anywhere;

• $$$2$$$ can be covered by at most $$$4$$$ submatrices. To achieve the maximum, it can only be put in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$;

• $$$3$$$ can be covered by at most $$$9$$$ submatrices. To achieve the maximum, it can only be put in area $$$(3,3)$$$ to $$$(n-2,n-2)$$$;

• $$$\ldots$$$

Consider $$$m = n, n-1, \ldots, \left\lfloor \frac{n}{2} \right\rfloor + 1$$$.

• $$$n$$$ can be put anywhere;

• Consider $$$(n-1)$$$. The intersection of all $$$(n-1) \times (n-1)$$$ submatrices is in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$ so it can only be put in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$;

• $$$(n-2)$$$ can only be put in area $$$(3,3)$$$ to $$$(n-2,n-2)$$$;

• $$$\ldots$$$

Afterward, the problem transforms into a classic counting problem. We start placing numbers within a central $$$k \times k$$$ matrix (if $$$n$$$ is odd, $$$k=1$$$; otherwise $$$k=2$$$); subsequently, numbers are placed within a $$$(k+2) \times (k+2)$$$ matrix centered around the previous one, and so on.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<vector<ll>> adj,vv;
vector<ll> a,comp;

void dfs(ll x, ll p, ll val){
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x,val);
            if(a[i]==a[x] && a[i]==val && comp[i]!=comp[x]){
                ll xxx=comp[i];
                for(auto j:vv[comp[i]]){
                    vv[comp[x]].push_back(j);
                    comp[j]=comp[x];
                }
                vv[xxx].clear();
                for(auto j:vv[comp[x]]){
                    a[j]=2*a[j];
                }
            }
        }
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        a.clear();
        a.resize(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        ll mini=*min_element(a.begin(),a.end());
        bool ok=true;
        for(ll i=0;i<n;i++){
            if(a[i]%mini!=0) ok=false;
            a[i]=a[i]/mini;
        }
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        if(!ok) cout<<"NO\n";
        else{
            comp.clear();
            comp.resize(n);
            for(ll i=0;i<n;i++) comp[i]=i;
            vv.clear();
            vv.resize(n);
            for(ll i=0;i<n;i++) vv[i].push_back(i);
            ll i=1;
            while(i<=1e9){
                dfs(0,-1,i);
                i=i*2;
            }
            ll cnt=count(a.begin(),a.end(),a[0]);
            if(cnt==n) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=200010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N],fa[N];
ll sum[N];
vector<int>  v;
vector<int>  G[N];
unordered_map<int,int> del[N];

void DFS(int x,int pr)
{
	v.push_back(x); 
	fa[x]=pr;
	sum[x]=a[x];
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==pr||del[x][y]) continue;
		DFS(y,x);
		sum[x]+=sum[y];
	}
}

int split(int x)
{
	v.clear();
	DFS(x,0);
	int y=0;
	if(v.size()==1) return 1;
	for(int i=0;i<v.size();i++) if(2*sum[v[i]]==sum[x]) y=v[i];
	if(y)
	{
		del[y][fa[y]]=del[fa[y]][y]=1;
		return 1;
	}
	else return 0;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) G[i].clear(),del[i].clear();		
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int flg=1;
		for(int i=1;i<LOGN;i++){
			for(int j=1;j<=n;j++){
			    flg&=split(j);
			    if(!flg) break;
			}
		}
		printf("%s\n",flg?"YES":"NO");
	}
	
	return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,q;
ll   ans;
char s[N];
int  S[N];
set<int> ST[N];

//---------------------------------------------------------- 
//Segtree 1 

struct nod
{
	int l,r,mn;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree() {}
	
	void init()
	{
		build(&root,0,n,S);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->l=l;(*p)->r=r;(*p)->mn=0;
		(*p)->lc=(*p)->rc=NULL;
	}

	void build(nod **p,int L,int R,int x[])
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->mn=x[L];
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M,x);
		build(&(*p)->rc,M+1,R,x);
		(*p)->mn=min((*p)->lc->mn,(*p)->rc->mn);
	}
	
	void add(int x,int v)
	{
		_add(root,x,v);
	}
	
	void _add(nod *p,int x,int v)
	{
		if(p->l==p->r)
		{
			p->mn+=v;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(x<=M)     _add(p->lc,x,v);
		else 		 _add(p->rc,x,v);
		p->mn=min(p->lc->mn,p->rc->mn);
	}
	
	int querymn(int L,int R)
	{
		return _querymn(root,L,R);
	}
	
	int _querymn(nod *p,int L,int R)
	{
		if(p->l==L&&p->r==R) return p->mn;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _querymn(p->lc,L,R);
		else if(L>M) return _querymn(p->rc,L,R);
		else return min(_querymn(p->lc,L,M),_querymn(p->rc,M+1,R));
	}
}TR;

//---------------------------------------------------------- 

//---------------------------------------------------------- 
//Segtree 2

struct Dnod
{
	int l,r,sum;
	Dnod *lc,*rc;
};

struct Dynamic_Segtree
{
	Dnod *root;
	
 	Dynamic_Segtree() 
	{
		root=NULL;
	}
	
	void newnod(Dnod **p,int l,int r)
	{
		*p=new Dnod;
		(*p)->l=l;(*p)->r=r;(*p)->sum=0;
		(*p)->lc=(*p)->rc=NULL;
	}

	void add(int p,int v)
	{
		_add(&root,0,n,p,v);
	}
	
	void _add(Dnod **p,int L,int R,int pos,int val)
	{
		if(*p==NULL) newnod(p,L,R);
		if(L==R)
		{
			(*p)->sum+=val;
			return ;
		}
		int M=(L+R)>>1;
		if(pos<=M) _add(&(*p)->lc,L,M,pos,val);
		else       _add(&(*p)->rc,M+1,R,pos,val);
		(*p)->sum=0;
		if((*p)->lc!=NULL) (*p)->sum+=(*p)->lc->sum;
		if((*p)->rc!=NULL) (*p)->sum+=(*p)->rc->sum;
	}
	
	int getsum(int L,int R)
	{
		return _getsum(root,L,R);
	}
	
	int _getsum(Dnod *p,int L,int R)
	{
		if(p==NULL) return 0;
		if(p->l==L&&p->r==R) return p->sum;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _getsum(p->lc,L,R);
		else if(L>M) return _getsum(p->rc,L,R);
		else return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
	}
}DT[N];

//---------------------------------------------------------- 

int LBS(int pos,int val)
{
	int L=-1,R=pos,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(TR.querymn(M,pos)<val) L=M;
		else R=M;
	}
	return R;
}

int RBS(int pos,int val)
{
	int L=pos,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(TR.querymn(pos,M)<val) R=M;
		else L=M;
	}
	return L;
}

int countk(int l,int r,int k)
{
	return DT[k+n].getsum(l,r);
}

int main()
{
	scanf("%d%d%s",&n,&q,s);
	for(int i=1;i<=n;i++) S[i]=S[i-1]+(s[i-1]=='('?1:-1);
	TR.init();
	for(int i=0;i<=n;i++) DT[S[i]+n].add(i,1);
	for(int i=1;i<=n;i++)
		ans+=countk(LBS(i,S[i]),i,S[i])-1;
	for(int i=1;i<=q;i++)
	{
		int p;
		scanf("%d",&p);
		if(s[p-1]==s[p]) 
		{
			printf("%I64d%c",ans,i==q?'\n':' ');
			continue;
		}
		swap(s[p-1],s[p]);
		if(s[p]==')')	
		{
			int l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans-=(L+R);
			DT[S[p]+n].add(p,-1);
			S[p]+=2;
			TR.add(p,2);
			DT[S[p]+n].add(p,1);
			l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans+=(ll)L*R;
			l=LBS(p,S[p]-1),r=RBS(p,S[p]-1),L=countk(l,p,S[p]-1),R=countk(p,r,S[p]-1);
			ans+=(ll)L*R;
		}
		else
		{
			int l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans-=(ll)L*R;
			l=LBS(p,S[p]-1),r=RBS(p,S[p]-1),L=countk(l,p,S[p]-1),R=countk(p,r,S[p]-1);
			ans-=(ll)L*R;
			DT[S[p]+n].add(p,-1);
			S[p]-=2;
			TR.add(p,-2);
			DT[S[p]+n].add(p,1);
			l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans+=(L+R);
		}
		printf("%I64d%c",ans,i==q?'\n':' ');
	}

	return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,q;
int a[N],x[N],pre_height[N],suf_height[N];
vector<pair<int,int> > pr;

//---------------------------------------------------------------------
//ST-Table Template

int lg2[N];
int mn[N][LOGN],mnpos[N][LOGN];

void build_ST()
{
	for(int i=1;i<=n;i++) lg2[i]=(int)log2(i);
	for(int i=1;i<=n;i++) mn[i][0]=pr[i].second,mnpos[i][0]=i;
	for(int i=1;i<LOGN;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p=j+(1<<(i-1));
			if(p>n) mn[j][i]=mn[j][i-1],mnpos[j][i]=mnpos[j][i-1];
			else    
			{
				mn[j][i]=min(mn[j][i-1],mn[p][i-1]);
				mnpos[j][i]=(mn[j][i-1]<mn[p][i-1])?mnpos[j][i-1]:mnpos[p][i-1];
			}
		}
	}
}

int getmin(int L,int R)
{
	int t=lg2[R-L+1];
	return min(mn[L][t],mn[R-(1<<t)+1][t]);
} 

int getminpos(int L,int R)
{
	int t=lg2[R-L+1];
	return mn[L][t]<mn[R-(1<<t)+1][t]?mnpos[L][t]:mnpos[R-(1<<t)+1][t];
} 
//---------------------------------------------------------------------

//---------------------------------------------------------------------
//Euler Sequence Template
int cnt;
int fa[N],dep[N],inid[N],ouid[N],euler_seq[N];
vector<int> G[N];

void DFS(int x,int pr)
{
	fa[x]=pr;
	dep[x]=dep[fa[x]]+1;
	inid[x]=(++cnt);
	euler_seq[inid[x]]=x;
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==fa[x]) continue;
		DFS(y,x);
	}
	ouid[x]=(++cnt);
	euler_seq[ouid[x]]=x;
}
//---------------------------------------------------------------------

//---------------------------------------------------------------------
//Segtree Template

struct nod
{
	int l,r,mx,tag;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree(int sz,int x[])
	{
		build(&root,1,sz,x);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->l=l;(*p)->r=r;(*p)->mx=(*p)->tag=0;
		(*p)->lc=(*p)->rc=NULL;
	}
	
	void pushdown(nod *p)
	{
		if(p->tag)
		{
			p->mx+=p->tag;
			if(p->l!=p->r) p->lc->tag+=p->tag,p->rc->tag+=p->tag;
			p->tag=0;
		}
	}
	
	void build(nod **p,int L,int R,int x[])
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->mx=dep[x[L]];	
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M,x);
		build(&(*p)->rc,M+1,R,x);
		(*p)->mx=max((*p)->lc->mx,(*p)->rc->mx);
	}
	
	void add(int L,int R,int v)
	{
		modify(L,R,v);
	}
	
	void modify(int L,int R,int v)
	{
		_modify(root,L,R,v);
	}
	
	void _modify(nod *p,int L,int R,int v)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->tag=v;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M)     _modify(p->lc,L,R,v);
		else if(L>M) _modify(p->rc,L,R,v);
		else
		{
			_modify(p->lc,L,M,v);
			_modify(p->rc,M+1,R,v);
		}
		pushdown(p->lc);
		pushdown(p->rc);
		p->mx=max(p->lc->mx,p->rc->mx);
	}
	
	int getmax(int L,int R)
	{
		return _querymx(root,L,R);
	}
	
	int _querymx(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R) return p->mx;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _querymx(p->lc,L,R);
		else if(L>M) return _querymx(p->rc,L,R);
		else return max(_querymx(p->lc,L,M),_querymx(p->rc,M+1,R));
	}
};

//---------------------------------------------------------------------

void input()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=q;i++) scanf("%d",&x[i]);
	pr.clear();
	pr.push_back(make_pair(0,0));
	for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i));
	sort(pr.begin(),pr.end());
}

void cal_fa(int L,int R,int FA)
{
	if(L>R) return ;
	int p=getminpos(L,R);
	fa[pr[p].second]=FA;
	cal_fa(L,p-1,pr[p].second);
	cal_fa(p+1,R,pr[p].second);
}

void build_tree()
{
	for(int i=1;i<=n;i++) G[i].clear();
	cal_fa(1,n,0);
	for(int i=2;i<=n;i++)
		G[i].push_back(fa[i]),G[fa[i]].push_back(i);
	cnt=0;	
	DFS(1,0);
}

void cal_pre()
{
	Segtree TR(2*n,euler_seq);
	for(int i=n;i;i--)
	{
		pre_height[i]=TR.getmax(1,2*n);
		int t=pr[i].second;
		TR.add(inid[t],inid[t],-n);
		TR.add(ouid[t],ouid[t],-n);
		TR.add(inid[t],ouid[t],-1);
	}
}

void cal_suf()
{
	Segtree TR(2*n,euler_seq);
	for(int i=1;i<=n;i++)
	{
		suf_height[i]=TR.getmax(1,2*n);
		int t=pr[i].second;
		TR.add(inid[t],inid[t],-n);
		TR.add(ouid[t],ouid[t],-n);
		TR.add(inid[t],ouid[t],-1);
	}
}

void solve()
{
	for(int i=1;i<=q;i++)
	{
		int L=0,R=n+1,M;
		while(L+1!=R)
		{
			M=(L+R)>>1;
			if(pr[M].first<x[i]) L=M;
			else R=M;
		}
		if(L==0) printf("%d",suf_height[1]);
		else if(L==n) printf("%d",pre_height[n]);
		else printf("%d",max(pre_height[L],suf_height[R]));
		printf("%c",i==q?'\n':' ');
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	 	input();
	 	build_ST();
	 	build_tree();
	 	cal_pre();
	 	cal_suf();
	 	solve();
	}
	
	return 0;
}