wa一片,最后一个T,终于心碎了。。。

为什么没人告诉我要开longlong

为什么所有人都说没有负数

 #include<cstdio>
#include<algorithm>
#define mid ((l+r)>>1)
using namespace std;
long long cas,a,b,c,k,l,r,n,m,sz;
int root[];
int ls[],rs[],sum[],lazy[];
void pushdown(int k,int l,int r)
{
if(!lazy[k]||l==r)return;
if(!ls[k])ls[k]=++sz;
if(!rs[k])rs[k]=++sz;
lazy[ls[k]]+=lazy[k];lazy[rs[k]]+=lazy[k];
sum[ls[k]]+=(mid-l+)*lazy[k];
sum[rs[k]]+=(r-mid)*lazy[k];
lazy[k]=;
}
void add(int k,int l,int r,int a,int b)
{
if(l==a&&r==b)
{
sum[k]+=r-l+;
lazy[k]++;
return;
}
pushdown(k,l,r);
if(a<=mid)ls[k]=ls[k]?ls[k]:++sz,add(ls[k],l,mid,a,min(b,mid));
if(b>mid)rs[k]=rs[k]?rs[k]:++sz,add(rs[k],mid+,r,max(mid+,a),b);
sum[k]=sum[ls[k]]+sum[rs[k]];
}
long long que(int k,int l,int r,int a,int b)
{
if(!k)return ;
if(l==a&&r==b)return sum[k];
pushdown(k,l,r);
if(b<=mid)return que(ls[k],l,mid,a,b);
else if(a>mid)return que(rs[k],mid+,r,a,b);
else return que(ls[k],l,mid,a,mid)+que(rs[k],mid+,r,mid+,b);
}
int solve()
{
int l=,r=*n,k=;
while(l!=r)
{
long long t=que(root[k<<|],,n,a,b);
if(c<=t)l=mid+,k=k<<|;
else r=mid,k=k<<,c-=t;
}
return l;
}
int main()
{
for(scanf("%d%d",&n,&m);m;m--)
{
scanf("%d%d%d%d",&cas,&a,&b,&c);
if(cas==)
for(k=,l=,r=*n,c+=n;l!=r;root[k]=root[k]?root[k]:++sz,add(root[k],,n,a,b))
if(c<=mid)r=mid,k=k<<;
else l=mid+,k=k<<|;
else printf("%d\n",solve()-n);
}
return ;
}

这次代码还是比较优美的

05-11 16:58