T1 BRS
题意：求区间最大连续子段和
题解：
60分做法：在每一段里贪心地做LIS，复杂度 <nobr> O(nm) </nobr>
100分做法：用线段树维护一个 lmax，rmax，max，sum，做区间合并即可
//by sdfzchy
#include<map>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define mp make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
int n,m;
const int maxn=500050;
inline int read()
{
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*f;
}
inline void print(int x)
{
if (x<0){putchar('-'); x=-x;}
if (x>=10) print(x/10);
putchar(x%10+'0');
}
struct segment_tree
{
struct tree_node{int sum,lmax,rmax,max;}t[maxn*4+5];
tree_node merge(tree_node lson,tree_node rson)
{
tree_node ret;
ret.sum=lson.sum+rson.sum;
ret.lmax=max(lson.lmax,lson.sum+rson.lmax);
ret.rmax=max(rson.rmax,rson.sum+lson.rmax);
ret.max=max(max(lson.max,rson.max),lson.rmax+rson.lmax);
return ret;
}
void Build(int l,int r,int rt)
{
if(l==r)
{
t[rt].max=read();
t[rt].lmax=t[rt].rmax=t[rt].sum=t[rt].max;
return;
}
int m=(l+r)>>1;
Build(l,m,rt<<1);
Build(m+1,r,rt<<1|1);
t[rt]=merge(t[rt<<1],t[rt<<1|1]);
}
void Update(int p,int x,int l,int r,int rt)
{
if(l==r)
{
t[rt].lmax=t[rt].rmax=t[rt].sum=t[rt].max=x;
return;
}
int m=(l+r)>>1;
if(p<=m) Update(p,x,l,m,rt<<1);
if(p>m) Update(p,x,m+1,r,rt<<1|1);
t[rt]=merge(t[rt<<1],t[rt<<1|1]);
}
tree_node Query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r) return t[rt];
int m=(l+r)>>1,flag=0;
tree_node ans;
if(L<=m) ans=Query(L,R,l,m,rt<<1),flag=1;
if(R>m) ans=flag?merge(ans,Query(L,R,m+1,r,rt<<1|1)):Query(L,R,m+1,r,rt<<1|1);
return ans;
}
}T;
int main()
{
freopen("BRS.in","r",stdin);
freopen("BRS.out","w",stdout);
n=read(),m=read();
T.Build(1,n,1);
for(int i=1,a,b,c;i<=m;i++)
{
a=read(),b=read(),c=read();
if(a==2) T.Update(b,c,1,n,1);
else printf("%d\n",T.Query(b,c,1,n,1).max);
}
return 0;
}T2 fyfy
题意：开始时在0处，每次走不超过k步，求到n的方案数
题解：很容易写出递推式 <nobr> f[i]=∑min(k,i)j=1f[i−j] </nobr>,发现这个东西是一个线性递推，矩阵加速即可，复杂度 <nobr> O(k3logn) </nobr>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int mod=7777777;
LL n;
int k;
struct Matrix
{
LL a[15][15];
Matrix() {memset(a,0,sizeof(a));}
Matrix operator *(const Matrix& b)const
{
Matrix ret;
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
for(int l=1;l<=k;l++)
ret.a[i][j]+=(a[i][l]*b.a[l][j])%mod;
return ret;
}
};
Matrix ksm(Matrix a,LL b)
{
b--;
Matrix ret;
ret=a;
for(;b;b>>=1,a=a*a)
{
if(b&1) ret=ret*a;
}
return ret;
}
void work()
{
Matrix ans,e;
ans.a[1][1]=1;
for(int i=1;i<=k;i++) e.a[1][i]=1;
for(int i=2;i<=k;i++) e.a[i][i-1]=1;
e=ksm(e,n);
ans=e*ans;
printf("%lld\n",ans.a[1][1]);
}
int main()
{
freopen("fyfy.in","r",stdin);
freopen("fyfy.out","w",stdout);
scanf("%d%lld",&k,&n);
work();
return 0;
}T3 olddriver
题意：求矩形面积并
题解：线段树扫描线，复杂度 <nobr> O(nlogn) </nobr>
ps:数据范围水，没写线段树，复杂度 <nobr> O(n2) </nobr>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL n,ecnt,ha[1000],vis[100010],ans;
struct seg
{
LL x,l,r,flag;
bool operator <(const seg& a)const
{
return x<a.x;
}
}e[1010];
int main()
{
freopen("olddriver.in","r",stdin);
freopen("olddriver.out","w",stdout);
scanf("%lld",&n);
LL a,b,c,d;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
ha[2*i-1]=a,ha[2*i]=c;
e[++ecnt].l=a,e[ecnt].r=c,e[ecnt].flag=1,e[ecnt].x=b;
e[++ecnt].l=a,e[ecnt].r=c,e[ecnt].flag=-1,e[ecnt].x=d;
}
sort(e+1,e+ecnt+1);
sort(ha+1,ha+2*n+1);
int m=unique(ha+1,ha+2*n+1)-ha-1;
for(int i=1;i<=ecnt;i++)
{
e[i].l=lower_bound(ha+1,ha+m+1,e[i].l)-ha;
e[i].r=lower_bound(ha+1,ha+m+1,e[i].r)-ha;
}
int sum=0;
for(int i=1;i<=ecnt;i++)
{
sum=0;
for(int j=1;j<=m;j++)
{
if(vis[j]>0) sum+=ha[j]-ha[j-1];
if(vis[j]<0) sum-=ha[j]-ha[j-1];
}
ans+=(e[i].x-e[i-1].x)*sum;
int tmp=e[i].x;
while(e[i].x==tmp)
{
for(int j=e[i].l+1;j<=e[i].r;j++)
vis[j]+=e[i].flag;
i++;
}
i--;
}
printf("%lld\n",ans);
return 0;
}又是一套信心题hhh
怎么感觉是线段树专题呢QAQ
京公网安备 11010502036488号