Author: loud_mouth
Idea: Bignubie
Editorial
Tutorial is loading...
Solution (Loud_mouth)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int last=0;
for(int i=0; i<30; ++i)
{
if(((n>>i)&1) == 1)
{
last=i;
}
}
cout<<(1<<last)-1<<"\n";
}
return 0;
}
Solution (the_nightmare)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define mii map<ll,ll>
#define msi map<string,ll>
#define mis map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N 200005
void solve()
{
ll n;
cin >> n;
ll cnt=0;
while(n!=0){
cnt++;
n=n/2;
}
cout << (1<<(cnt-1))-1 << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt","r",stdin);
#endif
ll int TEST=1;
cin >> TEST;
//init();
while(TEST--)
{
solve();
}
}
1527B1 - Palindrome Game (easy version)
Author: DenOMINATOR
Idea: shikhar7s
Editorial
Tutorial is loading...
Solution (DenOMINATOR)
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
bool is_palindrome=1;
int cnt_0 = 0;
for(int i=0;i<n;i++){
cnt_0 += s[i]=='0';
}
if(cnt_0 == 1){
cout << "BOB\n";
return;
}
if(cnt_0%2){
cout << "ALICE\n";
return;
}
cout << "BOB\n";
return;
}
signed main()
{
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Solution (shikhar7s)
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//const long double pi = acos(-1);
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
void shikhar7s(int cas)
{
int n,i;
cin>>n;
string s;
cin>>s;
int f=1,z=0;
fr(i,n)
{
if(s[i]=='0')
z++;
}
int x=0;
fr(i,n/2)
{
if(s[i]!=s[n-1-i])
{
f=0;
x++;
}
}
if(f)
{
if(z==1||z%2==0)
cout<<"BOB"<<endl;
else
cout<<"ALICE"<<endl;
}
else
{
if(x==1&&z==2)
cout<<"DRAW"<<endl;
else
cout<<"ALICE"<<endl;
}
}
signed main()
{
fast;
//freopen("input.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=1;
cin>>t;
int cas=1;
while(cas<=t)
{
//cout<<"Case #"<<cas<<": ";
shikhar7s(cas);
cas++;
}
return 0;
}
1527B2 - Palindrome Game (hard version)
Author: DenOMINATOR
Idea:DenOMINATOR
Editorial
Tutorial is loading...
Solution(Greedy) (DenOMINATOR)
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
bool is_palindrome=1;
int cnt_0 = 0, cnt_1 = 0;
for(int i=0;i<n;i++){
cnt_0 += s[i]=='0';
}
for(int i=0;i<n/2;i++){
if(s[i]!=s[n-1-i]) is_palindrome = 0;
if( (s[i]=='1' || s[n-1-i]=='1') && s[i]!=s[n-1-i]){
cnt_1++;
}
}
if(is_palindrome){
if(cnt_0 == 1){
cout << "BOB\n";
return;
}
if(cnt_0%2){
cout << "ALICE\n";
return;
}
cout << "BOB\n";
return;
}
if(cnt_0==2 && cnt_1==1){
cout << "DRAW\n";
return;
}
cout << "ALICE\n";
return;
}
signed main()
{
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Solution(DP) (DenOMINATOR)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double pi = acos(-1);
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int dp[505][505][2][2];
void precompute(){
for(int i=0;i<=500;i++){
for(int j=0;j<=500;j++){
for(int k=0;k<2;k++){
for(int l=1;l>=0;l--){
dp[i][j][k][l] = 1e9;
}
}
}
}
dp[0][0][0][0]=0;
dp[0][0][0][1]=0;
for(int i=0;i<=500;i++){
for(int j=0;j<=500;j++){
for(int k=0;k<2;k++){
for(int l=1;l>=0;l--){
if(l==0 && j>0) dp[i][j][k][l] = min(dp[i][j][k][l],-dp[i][j][k][1]);
if(i>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i-1][j+1][k][0]);
if(j>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j-1][k][0]);
if(k==1) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j][0][0]);
}
}
}
}
}
void solve(){
int n;
cin >> n;
string s;
cin >> s;
int cnt00=0,cnt01=0,mid=0;
for(int i=0;i<n/2;i++){
if(s[i]=='0' && s[i]==s[n-i-1]) cnt00++;
if(s[i]!=s[n-i-1]) cnt01++;
}
if(n%2 && s[n/2]=='0') mid=1;
if(dp[cnt00][cnt01][mid][0]<0){
cout << "ALICE";
}else if(dp[cnt00][cnt01][mid][0]>0){
cout << "BOB";
}else{
cout << "DRAW";
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
precompute();
int t;
cin >> t;
while(t--){
solve();
cout << "\n";
}
return 0;
}
Author: sharabhagrawal25
Idea: rivalq
Editorial
Tutorial is loading...
Solution (sharabhagrawal25)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[n];
for (int i = 0 ; i < n; i++){
cin >> a[i];
}
vector <long long> dp(n, 0);
map <long long,long long> value;
long long final_ans = 0;
for (long long i = 0 ; i < n ; i++){
if (i > 0) dp[i] = dp[i - 1];
if (value.count(a[i])){
dp[i] += value[a[i]];
}
value[a[i]] += (i + 1);
final_ans += dp[i];
}
cout << final_ans << endl;
}
}
Solution (mallick630)
t = int(input())
for j in range(t):
n = int(input())
a = list(map(int,input().split()))
value = {}
fa, ca = 0, 0
for i in range(n):
if a[i] in value:
ca += value[a[i]]
else:
value[a[i]]=0
value[a[i]] += i+1
fa += ca
print(fa)
Author: mallick630
Idea: CoderAnshu
Editorial
Tutorial is loading...
Solution (shikhar7s)
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define Endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const long double pi = acos(-1);
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
vector<int> adj[200005];
int vis[200005],c[200005],t;
pii p[200005];
void dfs(int x)
{
vis[x]=1;
c[x]=1;
int i;
p[x]=mp(t,t);
t++;
fr(i,sz(adj[x]))
{
if(!vis[adj[x][i]])
{
dfs(adj[x][i]);
c[x]+=c[adj[x][i]];
p[x].S=p[adj[x][i]].S;
}
}
}
void shikhar7s(int cas)
{
int n,i;
cin>>n;
t=0;
fr(i,n)
{
vis[i]=0;
adj[i].clear();
}
int x,y;
fr(i,n-1)
{
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(0);
int ans=0;
fr(i,sz(adj[0]))
{
int x=c[adj[0][i]];
x=(x*(x-1))/2;
ans+=x;
}
cout<<ans<<" ";
int s=0,ss=0,got=1;
y=-1;
fr(i,sz(adj[0]))
{
int x=c[adj[0][i]];
if(p[adj[0][i]].F<=p[1].F&&p[adj[0][i]].S>=p[1].S)
{
y=adj[0][i];
x-=c[1];
}
if(adj[0][i]!=y)
got+=x;
s+=x;
x*=x;
ss+=x;
}
ans=(s*s-ss)/2;
ans+=s;
cout<<ans<<" ";
i=2;
int l=0,r=1,j,b=0;
while(i<n)
{
if((p[i].F<=p[l].F&&p[i].S>=p[l].S)||(p[i].F<=p[r].F&&p[i].S>=p[r].S))
{
cout<<0<<" ";
i++;
continue;
}
if(!l)
{
int f=2;
ss=c[r];
if(p[r].F<=p[i].F&&p[r].S>=p[i].S)
{
f=1;
ss-=c[i];
}
if(!(p[y].F<=p[i].F&&p[y].S>=p[i].S))
{
ans=1;
fr(j,sz(adj[0]))
{
int x=adj[0][j];
if(x==y)
continue;
int su=c[x];
if(p[x].F<=p[i].F&&p[x].S>=p[i].S)
{
f=0;
su-=c[i];
}
ans+=su;
}
}
else
ans=got;
ans*=ss;
cout<<ans<<" ";
if(!f)
l=i;
else if(f==1)
r=i;
else
{
i++;
b=1;
break;
}
}
else
{
int f=2;
s=c[l];
ss=c[r];
if(p[l].F<=p[i].F&&p[l].S>=p[i].S)
{
f=0;
s-=c[i];
}
if(p[r].F<=p[i].F&&p[r].S>=p[i].S)
{
f=1;
ss-=c[i];
}
ans=s*ss;
cout<<ans<<" ";
if(!f)
l=i;
else if(f==1)
r=i;
else
{
i++;
b=1;
break;
}
}
i++;
}
if(!b)
cout<<1<<" ";
else
{
while(i<=n)
{
cout<<0<<" ";
i++;
}
}
cout<<endl;
}
signed main()
{
fast;
//freopen("output.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=1;
cin>>t;
int cas=1;
while(cas<=t)
{
//cout<<"Case #"<<cas<<": ";
shikhar7s(cas);
cas++;
}
return 0;
}
Solution (the_nightmare)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define mii map<ll,ll>
#define msi map<string,ll>
#define mis map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N 200005
ll add(ll x,ll y){return (x+y)%hell;}
ll mul(ll x,ll y){return (x*y)%hell;}
vector <ll> adj[N];
ll subtree[N];
ll min1[N];
ll ans[N];
ll vis[N];
ll le;
int v;int u;
ll n;
int prevv;int prevu;
void init(){
rep(i,0,n){
adj[i].clear();
subtree[i]=0;
min1[i]=n;
ans[i]=0;
vis[i]=0;
}
le=n*(n-1)/2;
v=0;u=0;
prevv=-1;
prevu=-1;
}
void dfs(int v,int prev=-1){
subtree[v]=1;
min1[v]=v;
for (auto it: adj[v]){
if (it==prev) continue;
dfs(it,v);
subtree[v]+=subtree[it];
min1[v]=min(min1[v],min1[it]);
}
}
void find(int val){
//cout << v << " " << u << " " << prevv << " " << prevu << " " << val << endl;
if (v==val or u==val){
ll a,b;
if (subtree[prevv]>subtree[v] or prevv==-1) a=subtree[v];
else a=n-subtree[prevv];
if (subtree[prevu]>subtree[u] or prevu==-1) b=subtree[u];
else b=n-subtree[prevu];
ans[val]=le-a*b;
//cout << a << " " << b << endl;
le=a*b;
return;
}
for (auto it: adj[v]){
if (it==prevv) continue;
if (min1[it]==val){
if (v==u) prevu=it;
prevv=v;
v=it;
vis[it]=1;
find(val);
return;
}
}
for (auto it: adj[u]){
if (it==prevu) continue;
if (min1[it]==val){
prevu=u;
u=it;
vis[it]=1;
find(val);
return;
}
}
ans[val]=le;
le=0;
}
void solve()
{
cin >> n;
init();
rep(i,0,n-1){
int x,y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(0);
//cout << le << endl;
for (auto it: adj[0]) {ans[0]+=(subtree[it]*(subtree[it]-1))/2;}
//cout << endl;
//cout << ans[0] << endl;
le-=ans[0];
rep(i,1,n){
if (vis[i]==1 or le==0) ans[i]=0;
else find(i);
}
ans[n]=le;
rep(i,0,n+1) cout << ans[i] << " ";
cout << endl;
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt","r",stdin);
#endif
ll int TEST=1;
cin >> TEST;
while(TEST--)
{
solve();
}
}
Editorial
Tutorial is loading...
Solution (rivalq)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
//#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
const int N = 5e4+5;
struct node{
int a=0;
node (int val=0){
a=val;
}
void merge(node &n1,node &n2){
this->a=min(n1.a,n2.a);
}
};
struct update{
int val=0;
update(int t=0){
val=t;
}
void combine(update &par,int tl,int tr){
val+=par.val;
}
void apply(node &node){
node.a+=val;
val=0;
}
};
template<typename node,typename update>
struct segtree{
node t[4*N];
bool lazy[4*N];
update zaker[4*N];
int tl[4*N];
int tr[4*N];
node nul;
inline void pushdown(int v){
if(lazy[v]){
apply(zaker[v],v);
lazy[v]=0;
zaker[v].apply(t[v]);
}
}
inline void apply(update &u,int v){
if(tl[v]!=tr[v]){
lazy[2*v]=lazy[2*v+1]=1;
zaker[2*v].combine(u,tl[2*v],tr[2*v]);
zaker[2*v+1].combine(u,tl[2*v+1],tr[2*v+1]);
}
}
void build(int v,int start,int end,int arr[]){
tl[v]=start;
tr[v]=end;
lazy[v]=0;
zaker[v].val = 0;
if(start==end){
t[v].a=arr[start];
}
else{
int m=(start+end)/2;
build(2*v,start,m,arr);
build(2*v+1,m+1,end,arr);
t[v].merge(t[2*v],t[2*v+1]);
}
}
void zeno(int v,int l,int r,update val){
pushdown(v);
if(tr[v]<l || tl[v]>r)return;
if(l<=tl[v] && tr[v]<=r){
t[v].a+=val.val;
apply(val,v);
return;
}
zeno(2*v,l,r,val);
zeno(2*v+1,l,r,val);
t[v].merge(t[2*v],t[2*v+1]);
}
node query(int v,int l,int r){
if(tr[v]<l || tl[v]>r)return node(hell);
pushdown(v);
if(l<=tl[v] && tr[v]<=r){
return t[v];
}
node a=query(2*v,l,r);
node b=query(2*v+1,l,r);
node ans;
ans.merge(a,b);
return ans;
}
public:
node query(int l,int r){
return query(1,l,r);
}
void upd(int l,int r,update val){
return zeno(1,l,r,val);
}
};
segtree<node,update>seg;
int dp[101][N];
int solve(){
int n,k; cin >> n >> k;
vector<int>a(n+1);
rep(i,1,n+1){
cin >> a[i];
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k; j++){
dp[j][i] = hell;
}
}
dp[0][0] = 0;
seg.build(1,0,n,dp[0]);
for(int j = 1; j <= k; j++){
vector<int>last(n+1);
dp[j][0] = 0;
for(int i = 1; i <= n; i++){
if(last[a[i]] == 0){
last[a[i]] = i;
}
else{
seg.upd(0,last[a[i]]-1,i-last[a[i]]);
last[a[i]] = i;
}
dp[j][i] = seg.query(0,i-1).a;
}
seg.build(1,0,n,dp[j]);
}
cout << dp[k][n] << endl;
//cout << elasped_time << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("test.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;//cin>>t;
while(t--){
solve();
}
return 0;
}
Solution (the_nightmare)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define mii map<ll,ll>
#define msi map<string,ll>
#define mis map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define MAXN 35005
int tree1[4*MAXN];
int lazy[4*MAXN];
int s[MAXN];
void build(int node, int start, int end)
{
lazy[node]=0;
if(start == end)
{
// Leaf node will have a single element
tree1[node] = s[start];
//cout << tree1[node] << " ";
}
else
{
int mid = (start + end) / 2;
// Recurse on the left child
build(2*node, start, mid);
// Recurse on the right child
build(2*node+1, mid+1, end);
// Internal node will have the sum of both of its children
tree1[node] = min(tree1[2*node],tree1[2*node+1]);
}
}
void updateRange(int node, int start, int end, int l, int r, int val)
{
if (l>r) return;
if(lazy[node] != 0)
{
// This node needs to be updated
tree1[node] = tree1[node]+lazy[node]; // Update it
if(start != end)
{
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(start > end or start > r or end < l) // Current segment is not within range [l, r]
return;
if(start >= l and end <= r)
{
// Segment is fully within range
tree1[node] = tree1[node]+val;
if(start != end)
{
// Not leaf node
lazy[node*2] += val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val); // Updating left child
updateRange(node*2 + 1, mid + 1, end, l, r, val); // Updating right child
tree1[node] = min(tree1[node*2],tree1[node*2+1]); // Updating root with max value
}
ll queryRange(int node, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return hell; // Out of range
if(lazy[node] != 0)
{
// This node needs to be updated
tree1[node] = tree1[node]+lazy[node]; // Update it
if(start != end)
{
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(start >= l and end <= r) // Current segment is totally within range [l, r]
return tree1[node];
int mid = (start + end) / 2;
ll p1 = queryRange(node*2, start, mid, l, r); // Query left child
ll p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
return min(p1,p2);
}
void solve()
{
ll n,k;
cin >> n >> k;
int a[n];
rep(i,0,n) cin >> a[i];
int lastoc[n];
map <int,int> m1;
rep(i,0,n){
if (m1.find(a[i])==m1.end()) lastoc[i]=-1;
else lastoc[i]=m1[a[i]];
m1[a[i]]=i;
}
int dp[n][k+1];
dp[0][1]=0;
rep(i,1,n){
dp[i][1]=dp[i-1][1];
if (lastoc[i]!=-1) dp[i][1]+=i-lastoc[i];
}
rep(i,2,k+1){
rep(j,0,n) s[j]=dp[j][i-1];
build(1,0,n-1);
rep(j,0,i-1) dp[j][i]=hell;
dp[i-1][i]=0;
rep(j,i,n)
{
int lastj=lastoc[j];
if (lastj>0 and (i-2)<(lastj)) {
updateRange(1,0,n-1,i-2,lastj-1,j-lastj);
}
dp[j][i] = queryRange(1,0,n-1,i-2,j-1);
}
}
cout << dp[n-1][k] << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt","r",stdin);
#endif
ll int TEST=1;
//cin >> TEST;
//init();
while(TEST--)
{
solve();
}
}
}
