题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<cstdio>
using namespace std;
class __attribute__((packed)) leaf 
{
	public:
	long long val;
	int num;
	leaf():val(0),num(0){}
	leaf(const leaf &x):val(x.val),num(x.num){}
}treel[1300000];
class __attribute__((packed)) non_leaf:public leaf 
{
	public:
	int lson,rson;
	non_leaf():leaf(),lson(0),rson(0){}
}treenl[12400000];
class finder
{
	public:
	leaf & operator [] (int x) const
	{
		if(x<100000000)
		return treenl[x];
		else
		return treel[x-100000000];
	}
}tree;
int n,m,q,x,y,i,leafr,nleafr,num[400000],numt;
long long val,valz;
int build(int l,int r)
{
	int mid=(l+r)/2,s;
	if(l==r)
	{
		leafr++;
		s=leafr+100000000;
		if(l<=n)
		{
			tree[s].val=l*1ll*m;
			tree[s].num=1;
		}
		return s;
	}
	nleafr++;
	s=nleafr;
	treenl[s].lson=build(l,mid);
	treenl[s].rson=build(mid+1,r);
	tree[s].val=tree[treenl[s].lson].val+tree[treenl[s].rson].val;
	tree[s].num=tree[treenl[s].lson].num+tree[treenl[s].rson].num;
	return s;
}
long long out(int rt,int k,int l,int r)
{
	int mid=(l+r)/2,lnum,z;
	tree[rt].num--; 
	if(l==r)
	return tree[rt].val;
	if(treenl[rt].lson==0)
	{
		if(mid<=m-1)
		lnum=mid-l+1;
		else if(l<=m-1)
		lnum=m-1-l+1;
		else
		lnum=0;
	}
	else
	lnum=tree[treenl[rt].lson].num;
	if(k<=lnum)
	{
		if(treenl[rt].lson==0)
		{
			if(mid!=l)
			{
				nleafr++;
				treenl[rt].lson=nleafr;
			}
			else
			{
				leafr++;
				treenl[rt].lson=leafr+100000000;
			}
			tree[treenl[rt].lson].val=tree[rt].val;
			tree[treenl[rt].lson].num=lnum;
		}
		return out(treenl[rt].lson,k,l,mid);
	}
	else
	{
		if(treenl[rt].rson==0)
		{
			if(mid+1!=r)
			{
				nleafr++;
				treenl[rt].rson=nleafr;
			}
			else
			{
				leafr++;
				treenl[rt].rson=leafr+100000000;
			}
			tree[treenl[rt].rson].val=tree[rt].val+mid-l+1;
			if(r<=m-1)
			z=r-mid;
			else if(mid<=m-1)
			z=m-1-mid;
			else
			z=0;
			tree[treenl[rt].rson].num=z;
		}
		return out(treenl[rt].rson,k-lnum,mid+1,r);
	}
}
void in(int rt,int k,long long v,int l,int r)
{
	int mid=(l+r)/2,lnum,z;
	tree[rt].num++;
	if(l==r)
	{
		tree[rt].val=v;
		return;
	}
	if(treenl[rt].lson==0)
	{
		if(mid<=m-1)
		lnum=mid-l+1;
		else if(l<=m-1)
		lnum=m-1-l+1;
		else
		lnum=0;
	}
	else
	lnum=tree[treenl[rt].lson].num;
	if(k<=mid)
	{
		if(treenl[rt].lson==0)
		{
			if(mid!=l)
			{
				nleafr++;
				treenl[rt].lson=nleafr;
			}
			else
			{
				leafr++;
				treenl[rt].lson=leafr+100000000;
			}
			tree[treenl[rt].lson].val=tree[rt].val;
			tree[treenl[rt].lson].num=lnum;
		}
		in(treenl[rt].lson,k,v,l,mid);
	}
	else
	{
		if(treenl[rt].rson==0)
		{
			if(mid+1!=r)
			{
				nleafr++;
				treenl[rt].rson=nleafr;
			}
			else
			{
				leafr++;
				treenl[rt].rson=leafr+100000000;
			}
			tree[treenl[rt].rson].val=tree[rt].val+mid-l+1;
			if(r<=m-1)
			z=r-mid;
			else if(mid<=m-1)
			z=m-1-mid;
			else
			z=0;
			tree[treenl[rt].rson].num=z;
		}
		in(treenl[rt].rson,k,v,mid+1,r);
	}
}
main()
{
	scanf("%d%d%d",&n,&m,&q);
	nleafr=n;
	for(i=1;i<=n;i++)
	if(m>1)
	{
		treenl[i].val=(i-1)*1ll*m+1;
		treenl[i].num=m-1;
		num[i]=m-1;
	}
	build(1,600000);
	numt=n;
	for(i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		if(y!=m)
		{
			val=out(x,y,1,600000);
			valz=out(n+1,x,1,600000);
		}
		else
		val=out(n+1,x,1,600000);
		printf("%lld\n",val);
		if(y!=m)
		{
			in(x,num[x]+1,valz,1,600000);
			num[x]++;
		}
		in(n+1,numt+1,val,1,600000);
		numt++;
	}
}