10.24
凹了一晚上线段树,P3372,然后发现这个板子可以过树状数组,于是过了P3374和P3368,都是板子,改改就行了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int a[maxn+2];
struct tree
{
int l,r;
long long pre,add;
}t[4*maxn+2];
void bulid(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].pre=a[l];
return;
}
int mid=l+r>>1;
bulid(p*2,l,mid);
bulid(p*2+1,mid+1,r);
t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
void lazy(int p)
{
if(t[p].add)
{
t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
}
void change(int p,int x,int y,int z)
{
if(x<=t[p].l && y>=t[p].r)
{
t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
t[p].add+=z;
return;
}
lazy(p);
int mid=t[p].l+t[p].r>>1;
if(x<=mid) change(p*2,x,y,z);
if(y>mid) change(p*2+1,x,y,z);
t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
long long find(int p,int x,int y)
{
if(x<=t[p].l && y>=t[p].r) return t[p].pre;
lazy(p);
int mid=t[p].l+t[p].r>>1;
long long ans=0;
if(x<=mid) ans+=find(p*2,x,y);
if(y>mid) ans+=find(p*2+1,x,y);
return ans;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
bulid(1,1,n);
for(int i=1;i<=m;++i)
{
int q,x,y,z;
cin>>q;
if(q==1)
{
cin>>x>>y>>z;
change(1,x,y,z);
}
else
{
cin>>x>>y;
cout<<find(1,x,y)<<endl;
}
}
}
然后把J组T1过了,(考场没想出来)。
然后开颓,过了几个板子,不说了。
10.25
开概率期望,然后做了一个很水的概率期望P1297
code
#include<bits/stdc++.h>
using namespace std;
long long n,A,B,C,a[10000010];
void init()
{
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
a[i] = a[i] % C + 1;
}
int main()
{
double ans;
init();
a[n+1]=a[1];
for(int i=1;i<=n;++i)
{
ans+=1/double(max(a[i+1],a[i]));
}
printf("%.3f",ans);
}
咋这么短啊,恼了。
标签:pre,记录,int,d%,mid,long,add From: https://www.cnblogs.com/iNFiNiTE-ENERZY-Overdose-/p/17787932.html