写的链表,维护连续的一段人,但是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;
}