xujian @ 2019-09-26 17:25:55
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<complex>
#include<csignal>
#include<csetjmp>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<iomanip>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define maxn 1000000 + 5
#define maxm
#define ls (p<<1)
#define rs (p<<1|1)
#define lb(x) (x&(-x))
#define qmid ((l+r)>>1)
#define inf 123456789
#define iinf 1000000007
#define mod 10000000000000000
#define re register
#define il inline
#define rep(i,l,r) for(re int i=l;i<=r;++i)
#define dep(i,l,r) for(re int i=r;i>=l;--i)
#define nxt(i,u) for(int i=h[u];i;i=e[i].next)
#define mem(f,x) memset(f,x,sizeof(f))
#define file(a) freopen(#a".in","r",stdin); freopen(#a".out","w",stdout);
using namespace std;
typedef long long ll;
typedef double D;
using namespace std;
typedef long long lint;
lint n,m,p;
lint a[5001000];
lint read(){
char c;lint x=0,f=1;
c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return f*x;
}
void write(lint x){
if(x<0)putchar('-'),x=-x;
lint y=10,len=1;
while(y<=x)y*=10,len++;
while(len--)y/=10,putchar(x/y+48),x%=y;
putchar(' ');
}
struct QAQ{
string name;
int score;
}stu[110];
bool cmp(QAQ a,QAQ b){
return a.score>b.score;
}
struct node{
lint left,right;
lint data;
lint lazy1,lazy2;
}tree[5001000];
void build(lint i,lint l,lint r){
tree[i].left=l;tree[i].right=r;
tree[i].lazy2=0;tree[i].lazy1=1;
if(tree[i].left==tree[i].right){
tree[i].data=a[l];
return;
}
lint mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
return;
}
void pushdown1(lint i){
if(tree[i].lazy1==1)return;
tree[i<<1].lazy1=(tree[i<<1].lazy1*tree[i].lazy1)%p;
tree[i<<1|1].lazy1=(tree[i<<1|1].lazy1*tree[i].lazy1)%p;
tree[i<<1].lazy2=(tree[i<<1].lazy2*tree[i].lazy1)%p;
tree[i<<1|1].lazy2=(tree[i<<1|1].lazy2*tree[i].lazy1)%p;
tree[i<<1].data=tree[i<<1].data*tree[i].lazy1%p;
tree[i<<1|1].data=tree[i<<1|1].data*tree[i].lazy1%p;
tree[i].lazy1=1;
return;
}
void pushdown2(lint i){
if(tree[i].lazy2==0)return;
tree[i<<1].lazy2=(tree[i<<1].lazy2+tree[i].lazy2)%p;
tree[i<<1|1].lazy2=(tree[i<<1|1].lazy2+tree[i].lazy2)%p;
tree[i<<1].data=(tree[i<<1].data+(tree[i<<1].right-tree[i<<1].left+1)*tree[i].lazy2%p)%p;
tree[i<<1|1].data=(tree[i<<1|1].data+(tree[i<<1|1].right-tree[i<<1|1].left+1)*tree[i].lazy2%p)%p;
tree[i].lazy2=0;
return;
}
void modify1(lint i,lint l,lint r,lint k){
if(tree[i].left>r||tree[i].right<l)return;
if(tree[i].left>=l&&tree[i].right<=r){
pushdown1(i);
pushdown2(i);
tree[i].lazy1=(tree[i].lazy1*k)%p;
tree[i].data=tree[i].data*k%p;
return;
}
pushdown1(i);
pushdown2(i);
modify1(i<<1,l,r,k);
modify1(i<<1|1,l,r,k);
tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
return;
}
void modify2(lint i,lint l,lint r,lint k){
if(tree[i].left>r||tree[i].right<l)return;
if(tree[i].left>=l&&tree[i].right<=r){
pushdown1(i);
pushdown2(i);
tree[i].lazy2=(tree[i].lazy2+k)%p;
tree[i].data=(tree[i].data+(tree[i].right-tree[i].left+1)*k%p)%p;
return;
}
pushdown1(i);
pushdown2(i);
modify2(i<<1,l,r,k);
modify2(i<<1|1,l,r,k);
tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
return;
}
lint query(lint i,lint l,lint r){
if(tree[i].left>r||tree[i].right<l)return 0;
if(tree[i].left>=l&&tree[i].right<=r)return tree[i].data%p;
pushdown1(i);
pushdown2(i);
tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
return query(i<<1,l,r)+query(i<<1|1,l,r);
}
void quicksort(int left,int right){
int i,j,base;
i=left;j=right;
base=a[(i+j)/2];
while(i<=j){
while(a[i]<base)i++;
while(a[j]>base)j--;
if(i<=j){
int t=a[i];
a[i]=a[j];a[j]=t;
i++;
j--;
}
}
if(left<j)quicksort(left,j);
if(i<right)quicksort(i,right);
}
int mian(){
n=1;m=2;p=2147483647;
for(lint i=1;i<=n;i++)a[i]=read();
build(1,1,n);
lint q,l,r,k;
for(lint i=1;i<=m;i++){
q=i==1?2:3;l=1;r=1;
if(q==1)k=read(),modify1(1,l,r,k%p);
else if(q==2)k=read(),modify2(1,l,r,k%p);
else write(query(1,l,r)%p);
}
return 0;
}
//刚好250行,完美AC <a+b problem> !
看了题解感觉自己十分的菜,于是蒟蒻想知道还有没有什么高级的算法QAQ
by Tarsal @ 2019-09-26 17:27:13
@xujian 苣!
by ✨USTCJYZ✨ @ 2019-09-26 17:28:37
int mian()。。。
by ♘GoldHookDream♞ @ 2019-09-26 17:31:46
flody
by xujian @ 2019-09-26 17:42:59
@eason0511 Floyd太菜了,不如dij
by xujian @ 2019-09-26 17:44:49
@eason0511 主要是Floyd和dij代码都太短了QAQ何况我还不会链式前向星/堆优化
by xujian @ 2019-09-26 17:45:07
写出来多丢人QAQ
by xujian @ 2019-09-26 17:45:41
@Flash_plus 您最巨好吗
by qwerty0862 @ 2019-09-26 17:45:43
%%%
by 1saunoya @ 2019-09-26 17:54:04
@xujian 学了两年+连最基本的东西都不会……这个有什么好显摆的。。。
by Ynoi @ 2019-09-26 18:01:40
@清风ღ Orz
我学了三年,啥都不会/kk