1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N=100005;
const ll inf=1LL<<60;
int n,m,i,x,y,s[N],q[N],t,left[N],right[N],lc[N],rc[N];char a[N];
int st,en,cnt[N<<1],last[N<<1];
ll sum,ans,two,L,R,MID,pre[N],suf[N];
P f[N];
inline void go(int l,int r){
  int i;
  while(st>l){
    st--;
    sum+=right[st]>=en?cnt[s[st]]:rc[st];
    cnt[s[st]]++;
  }
  while(en<r){
    en++;
    sum+=left[en]<=st?cnt[s[en]]:lc[en];
    cnt[s[en]]++;
  }
  while(st<l){
    cnt[s[st]]--;
    sum-=right[st]>=en?cnt[s[st]]:rc[st];
    st++;
  }
  while(en>r){
    cnt[s[en]]--;
    sum-=left[en]<=st?cnt[s[en]]:lc[en];
    en--;
  }
}
void solve(int l,int r,int dl,int dr){
  int mid=(l+r)>>1,dm;P best(inf,0);
  for(int i=dl;i<=dr;i++){
    go(i,mid);
    P now=f[i];
    now.first+=sum;
    if(now<best)best=now,dm=i;
  }
  best.first+=MID;
  best.second++;
  f[mid]=min(f[mid],best);
  if(l<mid)solve(l,mid-1,dl,dm);
  if(r>mid)solve(mid+1,r,dm,dr);
}
void cdq(int l,int r){
  if(l==r){
    //printf("dp[%d]=%lld %d\n",l,f[l].first,f[l].second);
    return;
  }
  int mid=(l+r)>>1;
  cdq(l,mid);
  sum=0;
  for(int i=l-1;i<=r;i++)cnt[s[i]]=0;
  cnt[s[st=en=l-1]]=1;
  solve(mid+1,r,l,mid);
  cdq(mid+1,r);
}
int main(){
  scanf("%d%d%s",&n,&m,a+1);
  s[0]=n;
  for(i=1;i<=n;i++)if(a[i]=='(')s[i]=s[i-1]+1;else s[i]=s[i-1]-1;
  /*s[l-1]==s[r] left[r]<=l-1 || right[l-1]>=r*/
  for(q[t=0]=i=0;i<=n;q[++t]=i++){
    while(t&&s[q[t]]>=s[i])t--;
    left[i]=q[t];
  }
  for(q[t=0]=i=n;~i;q[++t]=i--){
    while(t&&s[q[t]]>=s[i])t--;
    right[i]=q[t];
  }
  for(i=0;i<=n+n;i++)last[i]=-1;
  for(i=0;i<=n;i++){
    x=s[i];
    y=last[x];
    if(y>=left[i])lc[i]=lc[y]+1;
    last[x]=i;
    pre[i]=lc[i];
    if(i)pre[i]+=pre[i-1];
  }
  for(i=0;i<=n+n;i++)last[i]=n+1;
  for(i=n;~i;i--){
    x=s[i];
    y=last[x];
    if(y<=right[i])rc[i]=rc[y]+1;
    last[x]=i;
    suf[i]=rc[i];
    if(i<n)suf[i]+=suf[i+1];
  }
  ans=pre[n];
  if(m==1)return printf("%lld",ans),0;
  two=ans;
  for(i=1;i<n;i++)two=min(two,pre[i]+suf[i]);
  if(m==2)return printf("%lld",two),0;
  L=0,R=ans-two;
  while(L<=R){
    MID=(L+R)>>1;
    for(i=1;i<=n;i++)f[i]=P(inf,0);
    cdq(0,n);
    //printf("MID=%lld first=%lld second=%d\n",MID,f[n].first,f[n].second);
    if(f[n].second<=m){
      ans=f[n].first-MID*m;
      R=MID-1;
    }else{
      L=MID+1;
    }
  }
  printf("%lld",ans);
}