Problem solution [poi2009] Lyz ice skates

Luogu P3488

Brief meaning:

  • There are \ (n \) shoes in total, and there are \ (k \) pairs of shoes in each size. People with \ (x \) feet can wear shoes with \ (x,x+1,\dots\,x + d \)
  • \(m \) operation. Every time someone comes or leaves, judge whether everyone can match the shoes after each operation
  • \(n \le 2 \times 10^5,m \le 5 \times 10^5,1\le k \le 10^9\)

Practice:

If \ (s_i \) is the number of people with \ (I \) sign, it is obvious that for any interval \ ([l,r] \), it must meet \ (\ sum {I = l} ^ R s_i \ Le K \ times (R + D-L + 1) \)

Take the right side apart to get \ (\ sum_{i=l}^r s_i \le k \times (r-l+1) + k \times d \)

\ (\ sum_{i=l}^r s_i - k \le k \times d \)

To make the inequality hold, it is only necessary that the maximum value of \ (\ sum {I = l} ^ R s_i-k \) is less than or equal to \ (k \times d \).

Therefore, we need to maintain the maximum sub segment sum of the sequence \ (\ {s_i-k \} \).

If there is no modification operation, this is a very simple one DP question.

Let \ (f_i \) be the maximum field sum ending with \ (I \), and \ (g_i \) be the maximum field sum of the first \ (I \).

Then \ (f_i=f_{i-1}+s_i,g_i=max(g_{i-1},f_i) \), and \ (g_n \) is the maximum field sum of this sequence.

However, we need to modify the position back from the current sequence. However, the time complexity \ (O(nm) \) obviously cannot solve the problem, so consider using dynamic DP.

Consider how to optimize the modified recursive process. Obviously, the transfer equation of \ (f_i \) is a linear recursive formula, which can be accelerated by matrix, but there is an operation of taking max in the transfer equation of \ (g_i \) that cannot be transferred by matrix, so we need to redefine matrix multiplication.

As we all know, the traditional matrix multiplication is \ (C_{i,j}=\sum A_{i,k} \times B_{k,j} \), because the matrix multiplication satisfies the association law, we can speed up the operation by fast power.

Try to define the new matrix multiplication as \ (C {I, J} = max \ {a {I, K} + B {K, J} \}). It can be found that the new multiplication also satisfies the binding law.

After solving the problem of transfer, we can construct a matrix:

\(\begin{bmatrix}s_i&-inf&s_i\\s_i&0&s_i\\-inf&-inf&0\end{bmatrix} \times \begin{bmatrix}f_{i-1}\\g_{i-1}\\0\end{bmatrix} = \begin{bmatrix}f_i\\g_i\\0\end{bmatrix}\)

However, matrix alone is not enough. We need to quickly find the product of an interval to get the answer, but the transfer matrix of each position is different, so we can't find it with fast power.

To support single point modification and query interval product, we obviously want to maintain it with segment tree. We can put a matrix at each node of the segment tree to maintain the product of this interval. Each modification only needs to change the matrix of the corresponding leaf node, and then update the parent upward.

code:

#include <cstdio>
#include <algorithm>

using namespace std;

#define il inline
#define re register
#define file(s) freopen(#s".in","r",stdin),freopen(#s".out","w",stdout)

typedef long long ll;

const int N=5e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;

namespace FastIO
{
char buf[1<<21],buf2[1<<21],*p1=buf,*p2=buf;
int p4,p3=-1;
il int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
il void Flush(){fwrite(buf2,1,p3+1,stdout),p3=-1;}
#define isdigit(ch) (ch>=48&&ch<=57)
template <typename T>
il void read(T &x)
{
	re int f=0;x=0;re char ch=getc();
	while(!isdigit(ch)) f|=(ch=='-'),ch=getc();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getc();
	x=f?-x:x;
}
template <typename T>
il void print(T x)
{
	if(p3>(1<<20)) Flush();
	if(x<0) buf2[++p3]=45,x=-x;
	re int a[50]={};
	do{a[++p4]=x%10+48;}while(x/=10);
	do{buf2[++p3]=a[p4];}while(--p4);
}
}
using namespace FastIO;

/*Matrix part*/
struct mat{ll a[3][3];};
il void init(mat &x)
{
	for(re int i=0;i<3;++i)
		for(re int j=0;j<3;++j)
			x.a[i][j]=-inf;
	return;
}
il mat mul(const mat &x,const mat &y)
{
	re mat z;init(z);
	for(re int i=0;i<3;++i)
		for(re int j=0;j<3;++j)
			for(re int k=0;k<3;++k)
				z.a[i][j]=max(z.a[i][j],x.a[i][k]+y.a[k][j]);
	return z;
}
//New matrix multiplication

int n,m;
ll k,d,s[N];

/*Segment tree part*/
int L[N<<2],R[N<<2];
mat val[N<<2];
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define pushup(i) (val[i]=mul(val[ls(i)],val[rs(i)]))
il void build(int i,int l,int r)
{
	L[i]=l;R[i]=r;
	if(l==r)
	{
		val[i].a[0][0]=s[L[i]]; val[i].a[0][1]=-inf; val[i].a[0][2]=s[L[i]];
		val[i].a[1][0]=s[L[i]]; val[i].a[1][1]=0;    val[i].a[1][2]=s[L[i]];
		val[i].a[2][0]=-inf;    val[i].a[2][1]=-inf; val[i].a[2][2]=0;
		return;
	}
	re int mid=(l+r)>>1;
	build(ls(i),l,mid);build(rs(i),mid+1,r);
	pushup(i);return;
}//Build a tree
il void modify(int i,int p)
{
	if(L[i]==R[i])
	{
		val[i].a[0][0]=s[L[i]]; val[i].a[0][1]=-inf; val[i].a[0][2]=s[L[i]];
		val[i].a[1][0]=s[L[i]]; val[i].a[1][1]=0;    val[i].a[1][2]=s[L[i]];
		val[i].a[2][0]=-inf;    val[i].a[2][1]=-inf; val[i].a[2][2]=0;
		return;//Reset the matrix of leaf nodes
	}
	re int mid=(L[i]+R[i])>>1;
	modify(p>mid?rs(i):ls(i),p);
	pushup(i);return;
}//Single point modification

int main()
{
	read(n);read(m);read(k);read(d);
	for(re int i=1;i<=n;++i) s[i]=-k;
	build(1,1,n);
	for(re int i=1,r,x;i<=m;++i)
	{
		read(r),read(x);s[r]+=x;modify(1,r);
		puts(val[1].a[1][2]<=k*d?"TAK":"NIE");
        //The matrix of the root node is the answer of the whole sequence
	}
	Flush();return 0;
}

Posted by dv90 on Tue, 03 May 2022 22:05:53 +0300