关于ABC371 F
  • 板块学术版
  • 楼主Xdik
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/14 22:01
  • 上次更新2024/9/15 10:03:09
查看原帖
关于ABC371 F
700106
Xdik楼主2024/9/14 22:01

写的链表,维护连续的一段人,但是wa了18个,然后我打开评测记录一看,发现是最前面的18个点?!有没有人跟我一样的,或者能帮我找到错误的

#include <bits/stdc++.h>
#pragma GCC optimeze(3)
#pragma GCC optimeze(2)
#define int long long
#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
#define lowbit(x) (x & (-x))
using namespace std;
const int N=1e6+5;
const int M=6005; 
const int mod=19260817; 
const int INF=1e14;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans*=a,ans%=mod;
		a=a*a,a%=mod;
		b>>=1;
	} 
	return ans;
}
int n,tot,tr[N<<2],b[N<<2],ans;
struct llist{
	int lv,rv,la,ne,l,r;
}a[N*20];
void pushdown(int p){
	if(b[p]){
		tr[p<<1]=tr[p<<1|1]=b[p<<1]=b[p<<1|1]=b[p];
		b[p]=0;
	}
}
void add(int l,int r,int x,int p,int s,int t){
	if(s>=l&&t<=r){
		tr[p]=b[p]=x;
		return;
	}
	pushdown(p);
	int mid=(s+t)>>1;
	if(mid>=l)add(l,r,x,p<<1,s,mid);
	if(mid<r)add(l,r,x,p<<1|1,mid+1,t);
}
int qu(int x,int p,int s,int t){
	if(s==t)return tr[p];
	pushdown(p);
	int mid=(s+t)>>1;
	if(mid>=x)return qu(x,p<<1,s,mid);
	return qu(x,p<<1|1,mid+1,t); 
}//写个线段树维护每个人在哪个链表块里面 
void split(int x,int y){
	tot++;
	a[tot].lv=a[x].lv+y;
	a[tot].rv=a[x].rv;
	a[tot].l=a[x].l+y;
	a[tot].r=a[x].r;
	a[tot].la=x;
	a[tot].ne=a[x].ne;
	a[a[x].ne].la=tot;
	a[x].ne=tot;
	a[x].r=a[x].l+y-1;
	a[x].rv=a[x].lv+y-1;
	add(a[tot].l,a[tot].r,tot,1,1,n);
}//链表分裂 
void merge(int x,int y){
	tot++;
	a[tot].lv=a[x].lv,a[tot].rv=a[y].rv,a[tot].la=a[x].la,a[tot].ne=a[y].ne,a[tot].l=a[x].l,a[tot].r=a[y].r;
	a[a[x].la].ne=tot,a[a[y].ne].la=tot;
	add(a[tot].l,a[tot].r,tot,1,1,n);
}//链表合并 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		tot++;
		a[tot].lv=a[tot].rv=x;
		a[tot].la=tot-1;
		a[tot].ne=0;
		a[tot-1].ne=tot;
		a[tot].l=a[tot].r=i;
		add(i,i,tot,1,1,n);
	}
	int q;
	cin>>q;
	while(q--){
		int t,g;
		cin>>t>>g;
		int x=qu(t,1,1,n);
		if(a[x].lv+t-a[x].l<g&&t!=a[x].l)split(x,t-a[x].l),x=tot;
		if(a[x].lv+t-a[x].l>g&&t!=a[x].r)split(x,t-a[x].l+1);
		while(a[x].ne&&a[a[x].ne].lv<=g&&a[x].lv+t-a[x].l<g){
			ans+=(a[a[x].ne].lv-a[x].rv-1)*(a[x].r-a[x].l+1);
			merge(x,a[x].ne);
			a[tot].lv=a[tot].rv-(a[tot].r-a[tot].l);
			x=tot;
		}
		while(a[x].la&&a[a[x].la].rv>=g&&a[x].lv+t-a[x].l>g){
			ans+=(a[x].lv-a[a[x].la].rv-1)*(a[x].r-a[x].l+1);
			merge(a[x].la,x);
			a[tot].rv=a[tot].lv+(a[tot].r-a[tot].l);
			x=tot;
		}
		if(a[x].lv+t-a[x].l<g){
//			if(t!=a[x].l)split(x,t-a[x].l),x=tot;
			ans+=(a[x].r-a[x].l+1)*(g-a[x].lv);
			a[x].lv=g,a[x].rv=a[x].r-a[x].l+g;
		}
		if(a[x].lv+t-a[x].l>g){
//			if(t!=a[x].r)split(x,t-a[x].l+1);
			ans+=(a[x].r-a[x].l+1)*(a[x].rv-g);
			a[x].rv=g,a[x].lv=g-(a[x].r-a[x].l);
		}
	}
	cout<<ans;
	return 0;
}
2024/9/14 22:01
加载中...