枚举每个人，计算他必定是诚实者的情况下至少有几个人说谎，若超过$t$则他肯定是说谎者。

对于至少有几个人说谎，区间信息可以合并：

每个区间维护最左最右两个人$l,r$以及$f[i][j]$表示$l$和$r$诚实说谎状态分别为$i,j$时他们之间至少几个人说谎。

利用前缀和、后缀和可以在$O(1)$时间内求出每个人必定诚实时至少有几个人说谎。

时间复杂度$O(n)$。

 

#include
     
      #define rep(i) for(int i=0;i<2;i++)const int N=100010,inf=100000000;inline void up(int&a,int b){a>b?(a=b):0;}int Case,n,m,i,ans,mi,a[N];struct P{  int l,r,f[2][2];  void set(int x){    l=r=x;    rep(i)rep(j)f[i][j]=inf;    f[0][0]=0;    f[1][1]=1;  }  void must(int x){    l=r=x;    rep(i)rep(j)f[i][j]=inf;    f[0][0]=0;  }  P operator+(const P&b){    P c;    c.l=l,c.r=b.r;    rep(i)rep(j)c.f[i][j]=inf;    rep(i)rep(j)if(f[i][j]
      
       
        1)tmp=tmp+pre[i-1];      tmp=tmp+e[i];      if(tmp.f[0][0]>m)ans++,mi=i;    }    printf("%d %d\n",ans,mi);  }  return 0;}