P8010 「Wdsr-3」令人感伤的红雨

15pts

WA9 #6#7#8#10#11#16#17

TLE3 #18#19#20

#include<bits/stdc++.h>
using namespace std;
int n,q,mn,a[6000010],g[6000010],tag[6000010];
int las,f[6000010],nex[6000010],val[6000010];
int find(int x)
{
	if(x!=f[x]) return f[x]=find(f[x]);
	return x;
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=i;
		if(a[i]>=mn)
		{
			mn=a[i];
			g[i]=i;
			val[i]=mn;
			nex[i]=-1;
			nex[las]=i;
			las=i;
		}
		else
		{
			f[i]=f[i-1];
			g[i]=g[i-1];
		}
	}
	int op,x,y;
	while(q--)
	{
		cin>>op>>x>>y;
		if(op==1)
		{
			int fx=find(x),sum=0,u;
			tag[fx]+=y;
			sum+=tag[fx];
			for(u=nex[fx];u!=-1&&val[u]<val[fx]+sum;u=nex[u])
			{
				f[u]=fx;
				nex[fx]=nex[u];
				sum+=tag[u];
			}
		}
		else
		{
			cout<<max(0,x-g[find(y)])<<endl;
		}
	}
	return 0;
}