广东公务员考试成绩,密码锁防盗门,蔡小岑
【样例说明】
初始时数列为(1,2,3,4,5,6,7)。
经过第1次操作后,数列为(1,10,15,20,25,6,7)。
对第2次操作,和为10+15+20=45,模43的结果是2。
经过第3次操作后,数列为(1,10,24,29,34,15,16}
对第4次操作,和为1+10+24=35,模43的结果是35。
对第5次操作,和为29+34+15+16=94,模43的结果是8。
测试数据规模如下表所示
数据编号 1 2 3 4 5 6 7 8 9 10
N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline void read(ll& x) 5 { 6 x=0; 7 register char f=getchar(),c=0; 8 while(!isdigit(f)&&f!='-')f=getchar();if(f=='-')c=1,f=getchar(); 9 while(isdigit(f))x=x*10+(f^48),f=getchar();if(c)x=~x+1; 10 } 11 12 const int maxn=1e5+5; 13 14 struct node{ 15 ll l; 16 ll r; 17 ll sum; 18 ll jia; 19 ll ch; 20 }t[maxn*3]; 21 ll n,p,m; 22 ll a[maxn]; 23 24 25 inline void pushup(ll x) 26 { 27 t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%p; 28 } 29 30 inline void bt(ll x,ll l,ll r) 31 { 32 t[x].l=l; 33 t[x].r=r; 34 t[x].jia=0; 35 t[x].ch=1; 36 if(l==r) 37 { 38 t[x].sum=a[l]; 39 return ; 40 } 41 int mid=(l+r)>>1; 42 bt(x<<1,l,mid); 43 bt(x<<1|1,mid+1,r); 44 pushup(x); 45 } 46 47 inline void pushdown(ll x) 48 { 49 t[x*2].jia=(t[x*2].jia*t[x].ch+t[x].jia)%p; 50 t[x*2+1].jia=(t[x*2+1].jia*t[x].ch+t[x].jia)%p; 51 t[x*2].ch=(t[x*2].ch*t[x].ch)%p; 52 t[x*2+1].ch=(t[x*2+1].ch*t[x].ch)%p; 53 t[x*2].sum=(t[x].jia*(t[x*2].r-t[x*2].l+1)%p+t[x*2].sum*t[x].ch%p)%p; 54 t[x*2+1].sum=(t[x].jia*(t[x*2+1].r-t[x*2+1].l+1)%p+t[x*2+1].sum*t[x].ch%p)%p; 55 t[x].jia=0; 56 t[x].ch=1; 57 } 58 59 void updatec(ll x,ll l,ll r,ll w) 60 { 61 if(t[x].l>=l&&t[x].r<=r) 62 { 63 t[x].sum=t[x].sum*w%p; 64 t[x].jia=t[x].jia*w%p; 65 t[x].ch=t[x].ch*w%p; 66 } 67 else 68 { 69 pushdown(x); 70 int mid=(t[x].l+t[x].r)>>1; 71 if(mid>=l) 72 updatec(x<<1,l,r,w); 73 if(mid<r) 74 updatec(x<<1|1,l,r,w); 75 pushup(x); 76 } 77 return ; 78 } 79 80 void updatej(ll x,ll l,ll r,ll w) 81 { 82 if(t[x].l>=l&&t[x].r<=r) 83 { 84 t[x].jia=(t[x].jia+w)%p; 85 t[x].sum=((t[x].r-t[x].l+1)*w+t[x].sum)%p; 86 } 87 else 88 { 89 pushdown(x); 90 int mid=(t[x].l+t[x].r)>>1; 91 if(mid>=l) 92 updatej(x<<1,l,r,w); 93 if(mid<r) 94 updatej(x<<1|1,l,r,w); 95 pushup(x); 96 } 97 return ; 98 } 99 100 ll query(ll x,ll l,ll r) 101 { 102 if(t[x].r<=r&&t[x].l>=l) 103 { 104 return t[x].sum%p; 105 } 106 else 107 { 108 pushdown(x); 109 int ans=0; 110 int mid=(t[x].l+t[x].r)>>1; 111 if(mid>=l) 112 ans=query(x<<1,l,r)%p; 113 if(mid<r) 114 ans=ans+query(x<<1|1,l,r); 115 return ans%p; 116 } 117 } 118 119 int main() 120 { 121 read(n); 122 read(p); 123 for(int i=1;i<=n;i++) 124 { 125 read(a[i]); 126 } 127 bt(1,1,n); 128 read(m); 129 for(int i=1;i<=m;i++) 130 { 131 ll t,g,c,w; 132 cin>>w; 133 if(w==1) 134 { 135 read(t); 136 read(g); 137 read(c); 138 updatec(1,t,g,c); 139 } 140 if(w==2) 141 { 142 read(t); 143 read(g); 144 read(c); 145 updatej(1,t,g,c); 146 } 147 if(w==3) 148 { 149 read(t); 150 read(g); 151 printf("%lld\n",query(1,t,g)%p); 152 } 153 } 154 return 0; 155 }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论