447 D
题意
(n*m) 的矩阵， (k) 次操作：
- 给每一行减掉 (p)
- 给每一列减掉 (p)
求操作后矩阵所有元素总和的最大可能值。((1 ≤ n, m ≤ 10^3; 1 ≤ k ≤ 10^6; 1 ≤ p ≤ 100))
Examples
Input
2 2 2 2
1 3
2 4
Output
11
Input
2 2 5 2
1 3
2 4
Output
11
解
先预处理出①只操作行，且只操作 (i) 次②只操作列，且只操作 (i) 次（ (iin [1,10^6]) ）
然后丢到priority_queue贪心一波就行
447 E
题意
一个序列，两种操作
- 给区间 ([l,r]) 的每个元素 (a_i) 依次加上 (f_{i-l+1}) ( (f_i) 为斐波那契数列第 (i) 项， (f_1=f_2=1,f_3=2) )
- 询问区间的和
((1le nle 300000)) ， (\% 10^9+9)
Examples
Input
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
Output
17
12
解
线段树
Code
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define maxn 300010
#define mod 1000000009ll
#define INF 100000000000000000ll
using namespace std;
typedef long long D;
template<typename tp>
void read(tp& x){
x=0;
char c=getchar();
bool sgn=0;
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')sgn=1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
if(sgn)x=-x;
}
template<typename tp>
void write(tp x){
if(x<0)putchar('-'),write(-x);
else{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
}
D n,m;
D f[maxn],t[maxn<<2];
D z[maxn<<2][2];
D L(D x){return x>=mod?x%mod:x;}
void build(D p,D l,D r){
z[p][0]=z[p][1]=0;
if(l==r){
scanf("%lld",&t[p]);
return;
}
D mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p]=L(t[p<<1]+t[p<<1|1]);
}
D get(D A,D B,D i){
return i==1?A:L(L(f[i-2]*A)+L(f[i-1]*B));
}
D sum(D A,D B,D i){
return L(mod+get(A,B,i+2)-B);
}
D sum(D A,D B,D l,D r){
return L(mod+sum(A,B,r)-sum(A,B,l-1));
}
void pushdown(D p,D l,D r){
if(l==r){z[p][0]=z[p][1]=0;return;}
if(z[p][0]&&z[p][1]){
D mid=(l+r)>>1;
t[p<<1]=L(t[p<<1]+sum(z[p][0],z[p][1],1,mid-l+1));
t[p<<1|1]=L(t[p<<1|1]+sum(z[p][0],z[p][1],mid-l+2,r-l+1));
z[p<<1][0]=L(z[p<<1][0]+z[p][0]);
z[p<<1][1]=L(z[p<<1][1]+z[p][1]);
z[p<<1|1][0]=L(z[p<<1|1][0]+get(z[p][0],z[p][1],mid-l+2));
z[p<<1|1][1]=L(z[p<<1|1][1]+get(z[p][0],z[p][1],mid-l+3));
z[p][0]=z[p][1]=0;
}
}
void add(D p,D l,D r,D seg_l,D seg_r,D k){
pushdown(p,l,r);
if(seg_l<=l&&r<=seg_r){
z[p][0]=f[l-k+1],z[p][1]=f[l-k+2];
t[p]=L(t[p]+sum(z[p][0],z[p][1],1,r-l+1));
return;
}
D mid=(l+r)>>1;
if(seg_l<=mid)add(p<<1,l,mid,seg_l,seg_r,k);
if(seg_r>mid)add(p<<1|1,mid+1,r,seg_l,seg_r,k);
t[p]=L(t[p<<1]+t[p<<1|1]);
}
D query(D p,D l,D r,D seg_l,D seg_r){
pushdown(p,l,r);
if(seg_l<=l&&r<=seg_r){
return t[p];
}
D mid=(l+r)>>1;
D ret=0;
if(seg_l<=mid)ret=L(ret+query(p<<1,l,mid,seg_l,seg_r));
if(seg_r>mid)ret=L(ret+query(p<<1|1,mid+1,r,seg_l,seg_r));
return ret;
}
signed main(){
read(n);read(m);
f[1]=f[2]=1;
for(D i=3;i<maxn;i++){
f[i]=L(f[i-1]+f[i-2]);
}
build(1,1,n);
while(m--){
D mo,l,r;
read(mo);read(l);read(r);
if(mo==1){
add(1,1,n,l,r,l);
}
else{
write(query(1,1,n,l,r));
putchar('
');
}
}
return 0;
}