@[WGXWGXWGX](/user/463099)
>1≤k≤10^12
需要优化
by dn0pf902 @ 2021-09-20 12:56:38
@[dn0pf902](/user/347763) 怎么优化
by WGXWGXWGX @ 2021-09-20 12:57:02
@[WGXWGXWGX](/user/463099) 整块取
by dn0pf902 @ 2021-09-20 12:58:07
@[WGXWGXWGX](/user/463099) 栈不要存一个数值,存一段区间
by Carnival @ 2021-09-20 12:58:10
@[Gamemode](/user/316300) 可以给个示范吗??
by WGXWGXWGX @ 2021-09-20 13:05:25
@[dn0pf902](/user/347763) 可以给个示范吗??
by WGXWGXWGX @ 2021-09-20 13:06:48
@[WGXWGXWGX](/user/463099)
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[1000005],ans,k;
struct node{
int l,r;
ll sum;
node(){}
node(int _l,int _r,ll _s){
l=_l;
r=_r;
sum=_s;
}
};
void init(){
for(int i=1;i<=1000000;i++){
sum[i]=sum[i-1]+i;
}
}
int n,op,l,r;
stack<node> s;
int main(){
init();
cin>>n;
while(n--){
scanf("%d",&op);
if(op==1){
scanf("%d%d",&l,&r);
s.push(node(l,r,sum[r]-sum[l-1]));
}
if(op==2){
scanf("%lld",&k);
ll nw=0;
while(k-(s.top().r-s.top().l+1)>0){
nw+=s.top().sum;
k-=(s.top().r-s.top().l+1);
s.pop();
}
int nl=s.top().l,nr=s.top().r;
nw+=sum[nr]-sum[nr-k];
s.pop();
s.push(node(nl,nr-k,sum[nr-k]-sum[nl-1]));
printf("%lld\n",nw);
}
}
return 0;
}
```
我的代码
by dn0pf902 @ 2021-09-20 13:10:13
我的代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct tz {
int l,r;
} a[500002];
int ll,rr,i,n,op,sum,x,ans;
#undef int
int main() {
// freopen("stack2.in","r",stdin);
// freopen("stack2.ans","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
system("color 06");
cin>>n;
for(i=1; i<=n; ++i) {
cin>>op;
if(op==1) {
cin>>ll>>rr;
a[++sum].l=ll;
a[sum].r=rr;
} else {
ans=0;
cin>>x;
while(a[sum].r-a[sum].l+1<=x) {
x-=a[sum].r-a[sum].l+1;
ans+=(a[sum].l+a[sum].r)*(a[sum].r-a[sum].l+1)/2;
sum--;
}
if(x) {
ans+=(2*a[sum].r-x+1)*x/2;
a[sum].r-=x;
}
cout<<ans<<'\n';
}
}
return 0;
}
by Carnival @ 2021-09-20 13:11:57
@[Gamemode](/user/316300)
没有这两句还是会RE挂掉40分
```cpp
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
```
by KathyCao @ 2021-09-25 17:20:13
@[KathyCao](/user/319556) A 了,你说的 RE 有可能是因为洛谷日爆或者 system 的原因
by Carnival @ 2021-09-25 17:35:19