12.2日记
今日主要复习&学习了一些基本的数据结构：树状数组，线段树，单调队列，单调栈，并做了一些简单例题。
树状数组
确实短小精悍。
能做的事情：
- 单点修改+区间查询和(BIT)
- 区间加减+单点查询和(BIT2)维护差分数列
- 区间加减+区间查询和(BIT3)维护差分数列+D[i]*(i-1)
模板题：
- 洛谷P3374：单点加减+区间求和
//单点修改+区间查询和
#include<bits/stdc++.h>
using namespace std;
const int M=5e5+20;
int num_bit,a[M],c[M];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int k){
while(x<=num_bit)
c[x]+=k,x+=lowbit(x);
}
inline int query(int x){//1-x的和
int ans=0;
while(x)
ans+=c[x],x-=lowbit(x);
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
num_bit=n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),update(i,a[i]);
for(int i=1;i<=m;++i){
int op,y,z;
scanf("%d%d%d",&op,&y,&z);
if (op==1)
update(y,z);
else
printf("%d
",query(z)-query(y-1));
}
return 0;
}
- P3368：区间加减+单点询问
//区间修改+单点查询和
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+20;
int num_bit,a[M],d[M];
int sum1[M];
inline int lowbit(int x){return x&(-x);}
inline void update(int i,int k){
while(i<=num_bit)
d[i]+=k,i+=lowbit(i);
}
inline int query(int i){//求1-i的D和，即a[i]的值
int ans=0;
while(i)
ans+=d[i],i-=lowbit(i);
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
num_bit=n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),update(i,a[i]-a[i-1]);
for(int i=1;i<=m;++i){
int op,x,y,k;
scanf("%d",&op);
if (op==1)
scanf("%d%d%d",&x,&y,&k),update(x,k),update(y+1,-k);
else
scanf("%d",&x),printf("%d
",query(x));
}
return 0;
}
- POJ3468：区间加减+区间求和
//区间修改+区间查询和
#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int M=1e6+20;
int num_bit,a[M];
LL di[M],d[M];
inline int lowbit(int x){return x&(-x);}
inline void update(int i,LL k){
int x=i;
while(i<=num_bit)
d[i]+=k,di[i]+=k*(x-1),i+=lowbit(i);
}
inline LL query(int i){//求1-i的a和
LL ans=0,x=i;
while(i)
ans+=1LL*x*d[i]-di[i],i-=lowbit(i);
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
num_bit=n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),update(i,a[i]-a[i-1]);
for(int i=1;i<=m;++i){
int x,y,k;
getchar();
char op=getchar();
if (op=='C')
scanf("%d%d%d",&x,&y,&k),update(x,k),update(y+1,-k);
else
scanf("%d%d",&x,&y),printf("%lld
",query(y)-query(x-1));
}
return 0;
}
一道例题：
- 洛谷P1972。项链题，离线询问区间不同数个数。
构造：右端点从小到大排序。每个数最后一次出现的位置记为1，其余为0。则区间和即为不同数个数。
实现：设置last数组，last[i]表示i上一次出现的位置。这样输入一个数就先删掉上一个，再把这一个变成1。
注意：离线处理，排序时要用结构体，多加一个输入编号。依次处理的时候只要直接赋值ans[输入编号]，最后依次输出即可。
//洛谷，区间不同数个数，离线
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+20;
int num_bit,a[M],c[M],last[M],ans[M];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int k){
while(x<=num_bit)
c[x]+=k,x+=lowbit(x);
}
inline int query(int x){//1-x的和
int ans=0;
while(x)
ans+=c[x],x-=lowbit(x);
return ans;
}
struct Seg{
int l,r,no;
Seg(int a=0,int b=0,int c=0):l(a),r(b),no(c){}
bool operator<(Seg x){
return r<x.r;
}
}seg[M];
int main(){
int n;
scanf("%d",&n);
num_bit=n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int m;
scanf("%d",&m);
for(int i=1;i<=m;++i)
scanf("%d%d",&seg[i].l,&seg[i].r),seg[i].no=i;
sort(seg+1,seg+m+1);
int p=0;
for(int i=1;i<=m;++i){
while(p<seg[i].r){
++p;
update(p,1);
if(last[a[p]])
update(last[a[p]],-1);
last[a[p]]=p;
}
ans[seg[i].no]=query(seg[i].r)-query(seg[i].l-1);
}
for(int i=1;i<=m;++i)
printf("%d
",ans[i]);
return 0;
}
总结：
树状数组基本到此为止，只要背模板直接套用即可。看起来并不需要精通原理。
线段树
最终还是用了wzk的风格，即每次只修改lazy，pushdown操作先修改当前节点，再将lazy下放到儿子。
三道例题：
- P3372：区间加减+区间查询和
#include<bits/stdc++.h>
#define mid (l+r)/2
#define LL long long
using namespace std;
const int M=1e5+20;
LL v[4*M],a[M],lazy[4*M];
inline void push_up(int id,int l,int r){
v[id]=v[id*2]+lazy[id*2]*(mid-l+1)+v[id*2+1]+lazy[id*2+1]*(r-mid);
}
inline void push_down(int id,int l,int r){
lazy[id*2]+=lazy[id],
lazy[id*2+1]+=lazy[id],
v[id]+=lazy[id]*(r-l+1),
lazy[id]=0;
}
void build_tree(int id,int l,int r){
if (l==r){
v[id]=a[l];
return;
}
build_tree(id*2,l,mid);
build_tree(id*2+1,mid+1,r);
push_up(id,l,r);
}
LL query(int id,int l,int r,int ql,int qr){
if (ql<=l&r<=qr)
return v[id]+lazy[id]*(r-l+1);
push_down(id,l,r);
LL ans=0;
if (ql<=mid)
ans+=query(id*2,l,mid,ql,qr);
if (mid<qr)
ans+=query(id*2+1,mid+1,r,ql,qr);
return ans;
}
void operate(int id,int l,int r,int ql,int qr,LL x){
if (ql<=l&&r<=qr){
lazy[id]+=x;
return;
}
push_down(id,l,r);
if (ql<=mid)
operate(id*2,l,mid,ql,qr,x);
if (qr>mid)
operate(id*2+1,mid+1,r,ql,qr,x);
push_up(id,l,r);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
build_tree(1,1,n);
for(int i=1;i<=m;++i){
int op;
scanf("%d",&op);
if (op==1){
LL x,y,k;
scanf("%lld%lld%lld",&x,&y,&k);
operate(1,1,n,x,y,k);
}
else{
LL x,y;
scanf("%lld%lld",&x,&y);
printf("%lld
",query(1,1,n,x,y));
}
}
return 0;
}
- P3373：区间加减乘+区间查询和
#include<bits/stdc++.h>
#define mid (l+r)/2
#define LL long long
using namespace std;
const int M=1e5+20;
LL v[4*M],a[M],lazy1[4*M],lazy2[4*M],P;
inline void push_up(int id,int l,int r){
v[id]=(v[id*2]*lazy1[id*2]+lazy2[id*2]*(mid-l+1)+v[id*2+1]*lazy1[id*2+1]+lazy2[id*2+1]*(r-mid))%P;
}
inline void push_down(int id,int l,int r){
v[id]=(v[id]*lazy1[id]+lazy2[id]*(r-l+1))%P;
lazy1[id*2]=lazy1[id*2]*lazy1[id]%P;
lazy1[id*2+1]=lazy1[id*2+1]*lazy1[id]%P;
lazy2[id*2]=(lazy2[id*2]*lazy1[id]+lazy2[id])%P;
lazy2[id*2+1]=(lazy2[id*2+1]*lazy1[id]+lazy2[id])%P;
lazy1[id]=1,lazy2[id]=0;
}
void build_tree(int id,int l,int r){
lazy1[id]=1,lazy2[id]=0;
if (l==r){
v[id]=a[l]%P;
return;
}
build_tree(id*2,l,mid);
build_tree(id*2+1,mid+1,r);
push_up(id,l,r);
}
LL query(int id,int l,int r,int ql,int qr){
if (ql<=l&r<=qr)
return (v[id]*lazy1[id]+lazy2[id]*(r-l+1))%P;
push_down(id,l,r);
LL ans=0;
if (ql<=mid)
ans=(ans+query(id*2,l,mid,ql,qr))%P;
if (mid<qr)
ans=(ans+query(id*2+1,mid+1,r,ql,qr))%P;
return ans;
}
void operate1(int id,int l,int r,int ql,int qr,LL x){
if (ql<=l&&r<=qr){
lazy1[id]=lazy1[id]*x%P;
lazy2[id]=lazy2[id]*x%P;
return;
}
push_down(id,l,r);
if (ql<=mid)
operate1(id*2,l,mid,ql,qr,x);
if (qr>mid)
operate1(id*2+1,mid+1,r,ql,qr,x);
push_up(id,l,r);
}
void operate2(int id,int l,int r,int ql,int qr,LL x){
if (ql<=l&&r<=qr){
lazy2[id]=(lazy2[id]+x)%P;
return;
}
push_down(id,l,r);
if (ql<=mid)
operate2(id*2,l,mid,ql,qr,x);
if (qr>mid)
operate2(id*2+1,mid+1,r,ql,qr,x);
push_up(id,l,r);
}
int main(){
int n,m;
scanf("%d%d%d",&n,&m,&P);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
build_tree(1,1,n);
for(int i=1;i<=m;++i){
int op;
scanf("%d",&op);
if (op==1){
LL x,y,k;
scanf("%lld%lld%lld",&x,&y,&k);
operate1(1,1,n,x,y,k);
}
else if (op==2){
LL x,y,k;
scanf("%lld%lld%lld",&x,&y,&k);
operate2(1,1,n,x,y,k);
}
else{
LL x,y;
scanf("%lld%lld",&x,&y);
printf("%lld
",query(1,1,n,x,y));
}
}
return 0;
}
- P1198：单点修改+区间查询最大值
//单点插入+区间最大值
#include<bits/stdc++.h>
#define mid (l+r)/2
#define LL long long
using namespace std;
const int M=2e5+20;
int v[4*M],D;
char s[100];
LL lastans,endpos;
inline void push_up(int id,int l,int r){
v[id]=max(v[id*2],v[id*2+1]);
}
int query(int id,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr)
return v[id];
int ans=-2e9-100;
if (ql<=mid)
ans=max(ans,query(id*2,l,mid,ql,qr));
if (mid<qr)
ans=max(ans,query(id*2+1,mid+1,r,ql,qr));
return ans;
}
void operate(int id,int l,int r,int pos,int x){
if (l==r){
v[id]=x;
return;
}
if (pos<=mid)
operate(id*2,l,mid,pos,x);
else
operate(id*2+1,mid+1,r,pos,x);
push_up(id,l,r);
}
int main(){
LL ca;
int n;
scanf("%d%d",&n,&D);
for(int i=1;i<=n;++i){
scanf("%s",s);
if (s[0]=='A'){
scanf("%lld",&ca);
operate(1,1,n,++endpos,(lastans+ca)%D);
}
else{
LL ca;
scanf("%lld",&ca);
printf("%lld
",lastans=query(1,1,n,endpos-ca+1,endpos));
}
}
return 0;
}
注意：如果不同操作是用不同字母来代替的话，一定要按照%s字符串读入，不然会死的很惨……
总结：
线段树的题目每天都要做，明天找一下区间加减或修改+区间查询最大值的题目，一定要好好熟练pushdown怎么写，记得上次就是这道题调不出来，很难顶。
之后还有今天没写的题目，洛谷P2161。先按照自己的搜索写一下，之后再看看线段树染色的标解。
单调队列
今天学了学这两个单调数据结构，真是神仙……
思路：用双端队列。队首元素可能需要维护，一般队首元素为答案。每次从队尾插入元素之前，先检验是否从头到尾是单调的，否则就从队尾弹出元素，直到单调时再插入元素。
复杂度：(O(n))
能做的事情：
- （离线）求连续区间最值。
- 可以配合二分查找答案。
别的还在挖掘中……
一道例题：
- POJ2823。给1e6个数和k，从左到右依次输出长度为k的区间内的最大值和最小值。
若发现i<j&&a[i]>a[j]，如5 3，那么从最小值意义上讲，5已经毫无用处了，因此插入3之前就直接扔掉5。对最大值同理。
每次首先维护队首元素看是否在当前窗格内，否则弹出。之后从队尾插入元素时检验是否单调，到单调或空再插入。复杂度(O(n))。
注意：POJ上stl慢的一批，听说数组模拟队列很好用，回头学一下。
//滑动窗口最大最小值
#include<iostream>
#include<cstdio>
#include<utility>
#include<queue>
using namespace std;
const int M=1e6+20;
int a[M];
#define pii pair<int,int>
deque<pii> qmx,qmn;
inline char nc() {
static char buf[1000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int &sum) {
char ch = nc();
int tf = 0;
sum = 0;
while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();
tf = ((ch == '-') && (ch = nc()));
while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();
(tf) && (sum =- sum);
}
int main(){
int n,m;
read(n),read(m);
for(int i=1;i<=n;++i)
read(a[i]);
for(int i=1;i<=n;++i){
if (!qmn.empty()&&qmn.front().second+m==i)
qmn.pop_front();
while(!qmn.empty()&&qmn.back().first>=a[i])
qmn.pop_back();
qmn.push_back(pii(a[i],i));
if (i==m)
printf("%d",qmn.front().first);
else if (i>m)
printf(" %d",qmn.front().first);
}
putchar('
');
for(int i=1;i<=n;++i){
if (!qmx.empty()&&qmx.front().second+m==i)
qmx.pop_front();
while(!qmx.empty()&&qmx.back().first<=a[i])
qmx.pop_back();
qmx.push_back(pii(a[i],i));
if (i==m)
printf("%d",qmx.front().first);
else if (i>m)
printf(" %d",qmx.front().first);
}
putchar('
');
return 0;
}
单调栈
原理和单调队列差不多，只不过这次是在栈上操作，而不是双端队列。每次弹入元素之前先检验是否单调，到单调或空再弹入。答案可能在弹出时进行计算。和单调队列一样，一般插入时还需要配上位置（编号）
能做的事情：
- 左右第一个比某个位置的数大的数的位置，可以计算他们之间有几个数
- 给定序列，寻找子序列，使得最小值*序列长度最大。
- 给定序列，寻找子序列，使得最小值*序列元素和最大。
一道例题：
- POJ3250。奶牛题。每头牛能看到右边严格矮于它的牛的头型，设能看到c[i]头牛，问c[i]和。
单调栈，弹出的时候，被弹元素右边第一个比他大的数就是待插入元素，减去相应编号即可。同样也是离线处理。
//右侧第一个比他小的值的位置
#include<cstdio>
#include<utility>
#include<stack>
using namespace std;
const int M=1e5+20;
int h[M],ans[M];
#define pii pair<int,int>
#define LL long long
LL res;
void r_1max(int n){//需要ans,h数组
stack<pii> st;
for(int i=1;i<=n;++i){
while(!st.empty()&&st.top().first<=h[i])
ans[st.top().second]=i-st.top().second-1,st.pop();
st.push(pii(h[i],i));
}
while(!st.empty())
ans[st.top().second]=n-st.top().second,st.pop();
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&h[i]);
r_1max(n);
for(int i=1;i<=n;++i)
res+=ans[i];
printf("%lld
",res);
return 0;
}
总结：
单调数据结构的用处在于，如果在维护东西的时候，有很多冗余元素，比如没用的5，那么就可以利用单调性，进行删除，方便得出答案。这部分的例题还有很多，明天把那几道经典题都做了。
其他
今天还做了一个优先队列的，POJ2431卡车加油题。这个直接想到了，就不写了。主要还是贪心。
明日计划
- 线段树P2161，还有试炼场的另外一道题目
- 单调队列：HDU6319
- 单调栈：POJ2559，POJ3494，POJ2796,qz字符串CF1073G
最近半个月拼了！