我去怎么明天就考试了
今天没啥抽象事，就是分块入门9题我T1都没写过去非常恼
带修莫队没写出来，要是线段树就直接乱杀了，分块估计也能乱杀我非常恼
TLE的带修莫队
#include<bits/stdc++.h>
#define int long long
/* --------------- fast io --------------- */
using namespace std;
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{
template <typename T>
Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
template<class _Tp>
Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
template<class _Tp,class _tp>
Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
Reader(){}
}cin;
inline int read(){int n;cin>>n;return n;}
const char endl='\n';
struct Writer{
static const int set_precision = 6;
typedef int mxdouble;
template<typename T>
Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(char c){putchar(c);return*this;}
Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
template<class _Tp>
Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
template<class _Tp,class _tp>
Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}Writer(){}
}cout;
}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read Fastio::read
/* --------------- fast io --------------- */
int n,m,k,sqrtn,b[1000001],a[1000001],ans[1000001],K8=0,He=1;
class Mobius{
public:
int sum,bl[1000001];
class block{
public:
int l,r,id,k,t;
inline void Join(int li,int ri,int i,int time){
l=li,r=ri,
id=i,k=(li-1)/sqrtn+1;
t=time;
return;
}
inline bool operator<(block p){
if(k!=p.k)return l<p.l;
if(k&1)return r<p.r;
return r>p.r;
}
}blo[100001];
class change{
public:
int l,r,val,id;
inline void Join(int li,int ri,int i,int v){
l=li,r=ri,id=i,val=v;
}
}ch[100001];
inline void Join(int i){
int opt=read(),l=read(),r=read(),val=read();
if(opt==1)blo[++K8].Join(r,r,K8,He);
else ch[++He].Join(l,r,He,val);
return;
}
inline void Add(int i){
sum+=b[i];
}
inline void Del(int i){
sum-=b[i];
}
inline void Addt(int t,int l,int r){
for(int i=ch[t].l;i<=ch[t].r;i++)
b[i]+=ch[t].val;
// cout<<ch[t].val;
sum+=ch[t].val*(min(r,ch[t].r)-max(l,ch[t].l)+1);
// cout<<ch[t].val*(min(r,ch[t].r)-max(l,ch[t].l))<<endl;
//
}
inline void Delt(int t,int l,int r){
for(int i=ch[t].l;i<=ch[t].r;i++)
b[i]-=ch[t].val;
// cout<<ch[t].val;
sum-=ch[t].val*(min(r,ch[t].r)-max(l,ch[t].l)+1);
// cout<<ch[t].val*(min(r,ch[t].r)-max(l,ch[t].l))<<endl;
//
}
inline void Solve(){
sort(blo+1,blo+K8+1);
int l=1,r=0,t=1;
for(int i=1;i<=K8;++i){
// cout<<"case"<<i<<":"<<endl;
while(l>blo[i].l)
Add(--l);
// cout<<"sumADD1="<<sum<<endl;
while(r<blo[i].r)
Add(++r);
// cout<<"sumADD2="<<sum<<endl;
while(l<blo[i].l)
Del(l++);
// cout<<"sumDel1="<<sum<<endl;
while(r>blo[i].r)
Del(r--);
// cout<<"sumDel1="<<sum<<endl;
while(t<blo[i].t)
Addt(++t,blo[i].l,blo[i].r);
// cout<<"sumADDT1="<<sum<<endl;
while(t>blo[i].t)
Delt(t--,blo[i].l,blo[i].r);
// cout<<"sumDELT1="<<sum<<endl;
ans[blo[i].id]=sum;
// cout<<"sum="<<sum<<endl<<endl;
}
}
}bl;
signed main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
n=read();
sqrtn=sqrt(n);
for(int i=1;i<=n;i++)
b[i]=a[i]=read();
for(int i=1;i<=n;++i){
bl.Join(i);
}
bl.Solve();
for(int i=1;i<=K8;i++){
cout<<ans[i]<<endl;
}
}
感觉白给的原因是思路上比较暴力导致的
谁能帮我调调为啥似了数列分块1
然后就是我又去不了1机房了，洛谷再见
后面的到时候补