首页 > 编程札记 > 编程

2018 uestc training for data structures（智商恢复训练）

阅读：评论：0

本文参考自: 原文地址

集训前教练挂的一套题目。

教练说是基础题 em........

不得不佩服电子科大的训练题，质量是真的很高。

A 一颗简单的线段树

真简单的线段树模板题

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9+7;
ll ans1,ans2,ans3;
int n,m,a[maxn];
struct node
{int l,r,mid;ll sum,mx,mi;
}t[maxn<<2];
void pushup(int rt)
{t[rt].sum=t[lson].sum+t[rson].sum;t[rt].mx=max(t[lson].mx,t[rson].mx);t[rt].mi=min(t[lson].mi,t[rson].mi);
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r;t[rt].mid=mid;if(l==r){t[rt].mx=t[rt].mi=a[l];t[rt].sum=a[l];return ;}build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int pos,int val,int rt)
{if(t[rt].l==t[rt].r){t[rt].sum=t[rt].mx=t[rt].mi=val;return ;}if(pos<=t[rt].mid) update(pos,val,lson);else update(pos,val,rson);pushup(rt);
}
void query(int l,int r,int rt)
{if(l<=t[rt].l&&t[rt].r<=r){ans1+=t[rt].sum;ans2=max(ans2,t[rt].mx);ans3=min(ans3,t[rt].mi);return ;}if(l<=t[rt].mid) query(l,r,lson);if(r>t[rt].mid) query(l,r,rson);
}
int main()
{scanf("%d",&n);{build(1,n,1);scanf("%d",&m);while(m--){int flag,l,r;scanf("%d%d%d",&flag,&l,&r);if(flag==0) update(l,r,1);if(flag==1){ans1=0,ans2=-INF,ans3=INF;query(l,r,1);printf("%lldn",ans1-ans2-ans3);}}}
}

B 一颗普通的线段树

真普通的线段树就是区间更新的正常操作

需要注意 op的值是0或者其它刚开始以为是 0和1 被坑了好久

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9+7;
ll ans;
int n,m;
struct node
{int l,r,mid;ll sum,lazy;
}t[maxn<<2];
void pushdown(int rt)
{if(t[rt].lazy!=0){t[lson].sum+=t[rt].lazy*(t[lson].r-t[lson].l+1);t[lson].lazy+=t[rt].lazy;t[rson].sum+=t[rt].lazy*(t[rson].r-t[rson].l+1);t[rson].lazy+=t[rt].lazy;t[rt].lazy=0;}
}
void pushup(int rt)
{t[rt].sum=t[lson].sum+t[rson].sum;
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r;t[rt].mid=mid;if(l==r){t[rt].lazy=0;t[rt].sum=0;return ;}build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int l,int r,ll val,int rt)
{if(l<=t[rt].l&&t[rt].r<=r){t[rt].sum+=(val*(t[rt].r-t[rt].l+1));t[rt].lazy+=val;return ;}pushdown(rt);if(l<=t[rt].mid) update(l,r,val,lson);if(r>t[rt].mid) update(l,r,val,rson);pushup(rt);
}
void query(int l,int r,int rt)
{if(l<=t[rt].l&&t[rt].r<=r){ans+=t[rt].sum;return ;}pushdown(rt);if(l<=t[rt].mid) query(l,r,lson);if(r>t[rt].mid) query(l,r,rson);pushup(rt);
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){build(1,n,1);while(m--){int flag,l,r;ll v;scanf("%d%d%d%lld",&flag,&l,&r,&v);if(flag){ans=0;query(l,r,1);printf("%lldn",ans);}else update(l,r,v,1);}}//system("pause");
}

C 一颗像样的线段树

说实话有点难 = =

刚开始自己想了好久没想出来怎么做，然后看了下题解。。。

其实我们可以发现b数组最多就是1到n，那么我们对于1到n开一颗线段树，每个结点储存当前数出现的最后的位置。因为我们要求的是 i-ci到i-1的范围内没有出现过的第一个数，那么我们现在储存了每个数出现的最后的位置，那么我们就找一个这个位置不在i-ci到i-1的范围内且最小的数即可。因为我们线段树是默认1到n即从小到大，所以即尽可能地往左子树找，明白这个方法之后线段树的实现很简单。

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=1e6+5;
struct node
{int l,r,mid;int val;
}t[maxn<<2];
int n,c[maxn],b[maxn];
void pushup(int rt)
{t[rt].val=min(t[lson].val,t[rson].val);
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r,t[rt].mid=mid;if(l==r){t[rt].val=-1;return ;}build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int pos,int val,int rt)
{if(t[rt].l==t[rt].r){t[rt].val=val;return ;}if(pos<=t[rt].mid) update(pos,val,lson);else update(pos,val,rson);pushup(rt);
}
int query(int k,int rt)
{if(t[rt].l==t[rt].r)return t[rt].l;if(t[lson].val<k) return query(k,lson); //尽可能往左查else return query(k,rson);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&c[i]);build(1,n+1,1);update(1,0,1);  //1出现的最后位置是0for(int i=1;i<=n;i++){b[i]=query(i-c[i],1);update(b[i],i,1);}for(int i=1;i<=n;i++)printf("%d%c",b[i],i==n?'n':' ');//system("pause");
}

D 一颗复杂的线段树

这线段树确实很复杂= =

其实关键点在于如何实现l r区间的排序。死活想不到。。。

正解，二分答案，把比当前mid小的数置为0 大于等于mid的数置为1 ，然后区间的排序可以通过统计0 1的个数实现。最后check答案看是否符合要求

线段树的实现不是很复杂思路真的难想。

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,k,m,ans0,ans1,a[maxn];
struct Node
{int flag,l,r;
}q[maxn];
struct node
{int l,r,mid;int lazy,s1,s0;
}t[maxn<<2];
void pushdown(int rt)
{if(t[rt].lazy!=-1){t[lson].lazy=t[rson].lazy=t[rt].lazy;if(t[rt].lazy){t[lson].s0=0;t[lson].s1=t[lson].r-t[lson].l+1;t[rson].s0=0;t[rson].s1=t[rson].r-t[rson].l+1;}if(!t[rt].lazy){t[lson].s1=0;t[lson].s0=t[lson].r-t[lson].l+1;t[rson].s1=0;t[rson].s0=t[rson].r-t[rson].l+1;}t[rt].lazy=-1;}
}
void pushup(int rt)
{t[rt].s0=t[lson].s0+t[rson].s0;t[rt].s1=t[lson].s1+t[rson].s1;
}
void build(int l,int r,int val,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r,t[rt].mid=mid;t[rt].lazy=-1;if(l==r){t[rt].s0=t[rt].s1=0;if(a[l]>=val) t[rt].s1=1;else t[rt].s0=1;t[rt].lazy=-1;return ;}build(l,mid,val,lson);build(mid+1,r,val,rson);pushup(rt);
}
void update(int l,int r,int flag,int rt)
{if(l>r) return ;if(l<=t[rt].l&&t[rt].r<=r){t[rt].lazy=flag;if(flag){t[rt].s0=0;t[rt].s1=t[rt].r-t[rt].l+1;}if(!flag){t[rt].s1=0;t[rt].s0=t[rt].r-t[rt].l+1;}return ;}pushdown(rt);if(l<=t[rt].mid) update(l,r,flag,lson);if(r>t[rt].mid) update(l,r,flag,rson);pushup(rt);
}
bool query_1(int pos,int rt)    //判断当前点是否满足要求
{if(t[rt].l==t[rt].r){if(t[rt].s1==1) return 1;return 0;}pushdown(rt);if(pos<=t[rt].mid) return query_1(pos,lson);if(pos>t[rt].mid) return query_1(pos,rson);pushup(rt);
}
void query(int l,int r,int rt)   //查询l r 0 1 个数
{if(l<=t[rt].l&&t[rt].r<=r){ans0+=t[rt].s0;ans1+=t[rt].s1;return ;}pushdown(rt);if(l<=t[rt].mid) query(l,r,lson);if(r>t[rt].mid) query(l,r,rson);pushup(rt);
}
bool check(int x)   //二分答案
{build(1,n,x,1);for(int i=1;i<=m;i++){ans0=ans1=0;query(q[i].l,q[i].r,1);if(q[i].flag==0)    //通过区间更新实现区间排序{update(q[i].l,q[i].l+ans0-1,0,1);update(q[i].l+ans0,q[i].r,1,1);}if(q[i].flag==1){update(q[i].l,q[i].l+ans1-1,1,1);update(q[i].l+ans1,q[i].r,0,1);}}return query_1(k,1);
}
int main()
{while(scanf("%d%d",&n,&k)!=EOF){for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%d%d%d",&q[i].flag,&q[i].l,&q[i].r);int L=1,R=n,ans=1;while(L<=R){int mid=(L+R)>>1;if(check(mid)) ans=mid,L=mid+1;else R=mid-1;}printf("%dn",ans);}//system("pause");
}

E 小埋的steam愿望单

其实就是把string离散一下即可，但是这里的不合法情况较多，例如没有加入

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,ans,a[maxn];
string name;
vector<string> v;
int getid(string x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }
struct Node
{string name;int flag,val;
}q[maxn];
struct node
{int l,r,mid,flag,mx,mi;string namex,namei;
}t[maxn<<2];
void pushup(int rt)
{if(t[lson].mx>=t[rson].mx) t[rt].namex=t[lson].namex,t[rt].mx=t[lson].mx;else t[rt].namex=t[rson].namex,t[rt].mx=t[rson].mx;if(t[lson].mi<=t[rson].mi) t[rt].namei=t[lson].namei,t[rt].mi=t[lson].mi;else t[rt].namei=t[rson].namei,t[rt].mi=t[rson].mi;
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r,t[rt].mid=mid;t[rt].mx=-1,t[rt].mi=INF,t[rt].flag=0;if(l==r) return ;build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int pos,int val,int flag,string name,int rt)
{if(t[rt].l==t[rt].r){if(flag==-1){t[rt].mi=INF,t[rt].mx=-1,t[rt].flag=0; //删除return ;}if(flag==0&&t[rt].flag==0) return ; //不存在不能更新if(flag==1&&t[rt].flag==1) return ; //已经存在 不能添加t[rt].flag=1;t[rt].mx=t[rt].mi=val;t[rt].namex=t[rt].namei=name;return ;}if(pos<=t[rt].mid) update(pos,val,flag,name,lson);if(pos>t[rt].mid) update(pos,val,flag,name,rson);pushup(rt);
}
int main()
{while(scanf("%d",&n)!=EOF){v.clear();for(int i=1;i<=n;i++){scanf("%d",&q[i].flag);if(q[i].flag==1) cin>>q[i].name>>q[i].val,v.push_back(q[i].name);if(q[i].flag==2) cin>>q[i].name,v.push_back(q[i].name);if(q[i].flag==3) cin>>q[i].name>>q[i].val,v.push_back(q[i].name);if(q[i].flag==4) cin>>q[i].val;}sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end()); //离散化build(1,v.size()+1,1);for(int i=1;i<=n;i++){if(q[i].flag==1) update(getid(q[i].name),q[i].val,1,q[i].name,1);if(q[i].flag==2) update(getid(q[i].name),-1,-1,q[i].name,1);if(q[i].flag==3) update(getid(q[i].name),q[i].val,0,q[i].name,1);if(q[i].flag==4){if(q[i].val==1){ans=INF;if(t[1].mi==INF) continue;cout<<t[1].namei<<endl;}if(q[i].val==2){ans=-1;if(t[1].mx==-1) continue;cout<<t[1].namex<<endl;}}}}//system("pause");
}

F 好吃不过饺子

题目读懂以后其实就是暴力的线段树分别存最小值最大值总和即可，然后按照题意模拟

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,c,ans1,ans2,ans3,a[maxn],b[maxn];
string s1,s2;
vector<int> v;
int getid(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }
struct node
{int l,r,mid;int sum,ma,mi;
}t[maxn<<2];
void pushup(int rt)
{t[rt].mi=min(t[lson].mi,t[rson].mi);t[rt].ma=max(t[lson].ma,t[rson].ma);t[rt].sum=t[lson].sum+t[rson].sum;
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r,t[rt].mid=mid;if(l==r){t[rt].ma=t[rt].mi=t[rt].sum=b[l];return ;}build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void query(int l,int r,int rt)
{if(l<=t[rt].l&&t[rt].r<=r){ans1=max(ans1,t[rt].ma);ans2=min(ans2,t[rt].mi);ans3+=t[rt].sum;return ;}if(l<=t[rt].mid) query(l,r,lson);if(r>t[rt].mid) query(l,r,rson);
}
int main()
{scanf("%d%d",&n,&c);for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),v.push_back(a[i]);build(1,n,1);for(int i=1;i<=c;i++){string s1,s2;int len,res=0;cin>>s1>>s2>>len;for(int j=1;j<=n;j++){int L=getid(a[j]-len);  //注意一下左右的边界int R=getid(a[j])-1;ans1=-1,ans2=INF,ans3=0;if(s2=="min"){if(L>R) continue;else{query(L,R,1);if(s1=="gt"&&b[j]>ans2) res++;if(s1=="lt"&&b[j]<ans2) res++; }}if(s2=="max"){if(L>R) continue;                else{query(L,R,1);if(s1=="gt"&&b[j]>ans1) res++;if(s1=="lt"&&b[j]<ans1) res++;}}if(s2=="avg"){if(L>R) continue;else {query(L,R,1);if(s1=="gt"&&b[j]*(R-L+1)>ans3) res++;if(s1=="lt"&&b[j]*(R-L+1)<ans3) res++;}}}printf("%dn",res);}//system("pause");
}

G 三橙美琴的心里只有学习

简单的队列乱搞题刚开始没看到输入的t是递增的想了好久没想出来怎么做后来看别人代码发现默认按t的从小到大做的

仔细看了看题目发现真的有这个条件。。。

有这个条件的话我们可以把每个项目的完工时间加入队列，每次询问前把所以不合法的全部pop掉即可。

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,m;
int main()
{scanf("%d",&n);queue<pair<int,int>> que;for(int i=1;i<=n;i++){int flag,t,a,b;scanf("%d%d",&flag,&t);while(!pty()&&que.front().second<=t) que.pop();if(flag==1){scanf("%d%d",&a,&b);que.push({a,t+b});}if(flag==2) if(!pty()) que.pop();if(flag==3){pty()) printf("-1n");else printf("%dn",que.front().first);}}//system("pause");
}

H 中堂系的困难任务

刚开始自己看着公式瞎搞了好久怎么也跑不对答案，最后看题解发现是哈夫曼树 == 完全没看出来的我，至今不知道怎么推的，求大佬教= =

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n;
int main()
{int QAQ;scanf("%d",&QAQ);while(QAQ--){scanf("%d",&n);priority_queue<ll,vector<ll>,greater<ll> > que;ll x;for(int i=1;i<=n;i++) scanf("%lld",&x),que.push(x);ll ans=0;while(que.size()>1){ll a&#p();que.pop();ll b&#p();que.pop();ans+=(a+b);que.push(a+b);}printf("%lldn",ans);}//system("pause");
}

I 不如把并查集加个计数功能吧

简单的并查集操作多用一个数组记录每个联通块内的个数即可

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,m,q,par[maxn],num[maxn];
void init()
{for(int i=0;i<=n;i++) par[i]=i;for(int i=0;i<=n;i++) num[i]=1;
}
int find(int x)
{if(par[x]==x) return x;else return par[x]=find(par[x]);
}
bool same(int x,int y)
{int fx=find(x),fy=find(y);if(fx==fy) return 1;return 0;
}
void unite(int x,int y)
{if(same(x,y)) return ;int fx=find(x),fy=find(y);par[fx]=fy;num[fy]+=num[fx];   //计数更新
}
int main()
{scanf("%d%d",&n,&m);init();while(m--){int x,y;scanf("%d%d",&x,&y);unite(x,y);}scanf("%d",&q);while(q--){int x;scanf("%d",&x);printf("%dn",num[find(x)]);}//system("pause");
}

J 老头马桶枪

同食物链的那道题目几乎一样的操作，加权并查集。

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,m,q,par[maxn],ra[maxn];
void init()
{for(int i=0;i<=n;i++) par[i]=i;for(int i=0;i<=n;i++) ra[i]=0;
}
int find(int x)
{if(par[x]==x) return x;else{int px=find(par[x]);ra[x]=(ra[par[x]]+ra[x])%3;par[x]=px;}return par[x];
}
bool same(int x,int y)
{int fx=find(x),fy=find(y);if(fx==fy) return 1;return 0;
}
void unite(int x,int y,int d)
{if(same(x,y)) return ;int fx=find(x),fy=find(y);par[fx]=fy;ra[fx]=(d+ra[y]-ra[x]+3)%3;
}
int main()
{scanf("%d%d",&n,&m);init();int res=0,ans=-1;while(m--){int flag,x,y;scanf("%d%d%d",&flag,&x,&y);res++;if((x>n||y>n)&&ans==-1) ans=res%3;else if(flag==2&&x==y&&ans==-1) ans=res%3;else{if(same(x,y)){if((ra[x]-ra[y]+3)%3!=flag-1&&ans==-1) ans=res%3;}else unite(x,y,flag-1);}}if(ans==0) ans=3;printf("%dn",ans);//system("pause");
}

K 爱吃瓜的伊卡洛斯（1）

西瓜只有两种即非A即B 那么同样采用加权并查集即可。

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,m,q,par[maxn],ra[maxn];
void init()
{for(int i=0;i<=n;i++) par[i]=i;for(int i=0;i<=n;i++) ra[i]=0;
}
int find(int x)
{if(par[x]==x) return x;else{int px=find(par[x]);ra[x]=(ra[par[x]]+ra[x])%2;par[x]=px;}return par[x];
}
bool same(int x,int y)
{int fx=find(x),fy=find(y);if(fx==fy) return 1;return 0;
}
void unite(int x,int y,int d)
{if(same(x,y)) return ;int fx=find(x),fy=find(y);par[fx]=fy;ra[fx]=(d+ra[y]-ra[x]+2)%2;
}
int main()
{scanf("%d%d",&n,&m);init();while(m--){char c;int x,y,flag;scanf(" %c",&c);if(c=='A'){scanf("%d%d%d",&x,&y,&flag);unite(x,y,flag-1);}if(c=='Q'){int ans=0;scanf("%d%d",&x,&y);if(!same(x,y)) ans=3;else{if((ra[x]-ra[y]+2)%2==0) ans=1;else ans=2;   }printf("%dn",ans);}}//system("pause");
}

L 爱吃瓜的伊卡洛斯（2）

这个题目将西瓜的种类数扩展到了无数种，瞬间就不会做了。。。

解法是采用启发式合并，不过也没搞懂启发式合并是什么鬼，感觉就是自己写的合并= =

x y 如果是不同的瓜那么我们可以用set维护与x不同种类的瓜，insert到set[x]中，同样的y中也要推入x。

当他们是同一种类的瓜是将x和y连接，同时将他们的set合并，注意合并的时候可以只合并祖先来减少冗余。因为我们查找也是只查找祖先所以问题不大。之后询问如果是同一并查集则种类相同若在set可以找到则不相同其他情况为未知。

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=1e5+5;
const int INF=1e9+7;
int n,m,par[maxn];
char c;
set<int> s[maxn];
int find(int x)
{return par[x]==x? x : par[x]=find(par[x]);
}
void unite(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy){if(s[fx].size()>s[fy].size()) swap(fx,fy);par[fx]=fy; //并查集合并if(s[fx].size())    //跟x种类不同即跟y种类不同{for(auto it=s[fx].begin();it!=s[fx].end();it++){s[fy].insert(find(*it));}}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) par[i]=i;for(int i=1;i<=m;i++){int x,y,flag;scanf(" %c",&c);if(c=='A'){scanf("%d%d%d",&x,&y,&flag);if(flag==1) unite(x,y);if(flag==2){int fx=find(x),fy=find(y);if(fx!=fy){s[fx].insert(fy);s[fy].insert(fx);}}}else{scanf("%d%d",&x,&y);int fx=find(x),fy=find(y);if(s[fx].find(fy)!=s[fx].end()||s[fy].find(fx)!=s[fy].end()) printf("2n");else if(fx==fy) printf("1n");else printf("3n");}}//system("pause");
}

L 一道普通题1

这题根本一点不普通好吧开始想着用线段树做是真心不知道怎么做啊，后来瞄了一眼题解发现是分块= =

跟我之前做的分块不是一个级别的之前做的基本用线段树都可以很简单的实现，这个线段树实现不了啊，当时学分块看qsc大佬的视频学的，专门用了解决一些瞎鸡儿更新和瞎鸡儿查询的题目大概说的就是这些了= =

用了分块其实就相当于是暴力算法没啥好说的，

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
vector<int> s[1010];
int n,sz,pos[maxn],tag[maxn],a[maxn];
void add(int l,int r,int c)
{for(int i=l;i<=min(pos[l]*sz,r);i++) a[i]+=c;s[pos[l]].clear();  //对块进行重建for(int i=(pos[l]-1)*sz+1;i<=min(pos[l]*sz,n);i++) s[pos[i]].push_back(a[i]);sort(s[pos[i]].begin(),s[pos[i]].end());if(pos[l]==pos[r]) return ; //判断l r是否为同一块for(int i=pos[l]+1;i<=pos[r]-1;i++) tag[i]+=c;  //对块进行整体修改for(int i=(pos[r]-1)*sz+1;i<=r;i++) a[i]+=c;s[pos[r]].clear();for(int i=(pos[r]-1)*sz+1;i<=min(pos[r]*sz,n);i++) s[pos[i]].push_back(a[i]);sort(s[pos[i]].begin(),s[pos[i]].end());
}
int query(int l,int r,int c)
{int ans=-1;for(int i=l;i<=min(pos[l]*sz,r);i++)    //对于左右边界所在的块暴力搜索if(tag[pos[i]]+a[i]<c) ans=max(ans,tag[pos[i]]+a[i]);if(pos[l]==pos[r]) return ans;for(int i=(pos[r]-1)*sz+1;i<=r;i++)if(tag[pos[i]]+a[i]<c) ans=max(ans,tag[pos[i]]+a[i]);for(int i=pos[l]+1;i<=pos[r]-1;i++) //对中间块进行整体搜索{auto it=lower_bound(s[i].begin(),s[i].end(),c-tag[i]);if(it==s[i].begin()) continue;  //找不到跳过it--;ans=max(ans,*it+tag[i]);}return ans;
}
int main()
{while(scanf("%d",&n)!=EOF){sz=sqrt(n*1.0);for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[i]=(i-1)/sz+1;s[pos[i]].push_back(a[i]);}for(int i=1;i<=pos[n];i++) sort(s[i].begin(),s[i].end());for(int i=1;i<=n;i++){int flag,l,r,c;scanf("%d%d%d%d",&flag,&l,&r,&c);if(flag==0) add(l,r,c);if(flag==1) printf("%dn",query(l,r,c));}}//system("pause");
}

N 一道普通题2

这道题理论上应该是考察一个数被开方大概7次之后就是1这个知识点，不过我这里用了一种神奇的方法卡过去了，即对每一个结点打个标记，如果该叶结点的数被开方到1，那么就flag=1 如果区间flag都为1 则该区间flag=1 对于flag=1的区间之前返回区间结果即可。

这个方法理论上碰到那种0比较多的情况应该时间会很慢不过神奇的卡过去了

正常写线段树也可以，就是注意把0的情况考虑进去即可。

这里直接搬一年前的代码比较丑= =

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
const int maxn=5e4+5;
int n,m;
ll ans;
int a[maxn];
struct tree
{int l,r,mid;ll k;int cnt,flag;int mark;
}t[maxn<<2];
void pushdown(int rt)
{if(t[rt].mark==-1){t[lson]t += t[rt]t;t[rson]t += t[rt]t;t[lson].mark=t[rson].mark=-1;t[rt].mark=t[rt]t=0;}
}
void pushup(int rt)
{t[rt].k=t[lson].k+t[rson].k;if(t[lson].flag&&t[rson].flag)t[rt].flag=1;
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].mid=mid;t[rt].l=l;t[rt].r=r;t[rt]t=t[rt].mark=t[rt].flag=0;if(l==r){t[rt].k=a[t[rt].l];return ;}build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int l,int r,int rt)
{if(t[rt].flag) return ;if(l<=t[rt].l&&t[rt].r<=r){t[rt]t++;t[rt].mark=-1;if(t[rt].l==t[rt].r){for(int i=1;i<=t[rt]t;i++)t[rt].k=(int)sqrt(t[rt].k);t[rt]t=0;if(t[rt].k==1)t[rt].flag=1;}return ;}pushdown(rt);if(l<=t[rt].mid)update(l,r,lson);if(r>t[rt].mid)update(l,r,rson);pushup(rt);
}
void query(int l,int r,int rt)
{if(l<=t[rt].l&&t[rt].r<=r&&t[rt].flag){ans=ans+t[rt].k;return ;}if(l<=t[rt].l&&t[rt].r<=r&&t[rt].l==t[rt].r){for(int i=1;i<=t[rt]t;i++)t[rt].k=(int)sqrt(t[rt].k);t[rt]t=0;if(t[rt].k==1) t[rt].flag=1;ans=ans+t[rt].k;return ;}pushdown(rt);if(l<=t[rt].mid)query(l,r,lson);if(r>t[rt].mid)query(l,r,rson);pushup(rt);
}
int main()
{while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,n,1);int q,l,r,c;for(int i=0;i<n;i++){scanf("%d%d%d%d",&q,&l,&r,&c);if(q==0)update(l,r,1);if(q==1){ans=0;query(l,r,1);printf("%lldn",ans);}}}
}

O 帆宝RMQ

其实如果把M题做了的话这题应该还好，采用的也是分块的思想，直接分块以后暴力查找即可，中间要注意块的重建。

我这里找最左和最右直接用的lower_bound找到第一个数之后依次找和它相同的数并不断的更新l r ，其实这样是会被某些数据卡掉的，一种很简单的做法其实就是从左往右找第一个x，从右往左找第一个x 依次采用lower_bound 和 upper_bound即可实现，两种方法的对比时间差异不大，可能数据较弱，这里给出第一种

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=1e9+7;
struct node
{int val,idx;bool operator<(const node &p) const{if(val==p.val) return idx<p.idx;return val<p.val;}
}a[maxn];
vector<node> v[1010];
int n,q,sz,pos[maxn],tag[maxn];
void rebuild(int x)
{v[x].clear();for(int i=(x-1)*sz+1;i<=min(x*sz,n);i++)v[x].push_back(a[i]);sort(v[x].begin(),v[x].end());
}
void add(int l,int r,int c)
{for(int i=l;i<=min(pos[l]*sz,r);i++) a[i].val+=c;rebuild(pos[l]);if(pos[l]==pos[r]) return ;for(int i=pos[l]+1;i<pos[r];i++) tag[i]+=c;for(int i=(pos[r]-1)*sz+1;i<=r;i++) a[i].val+=c;rebuild(pos[r]);
}
int query(int x)
{int li=INF,ri=-INF;for(int i=1;i<=pos[n];i++){node k;k.idx=0,k.val=x-tag[i];auto it=lower_bound(v[i].begin(),v[i].end(),k);if(it==v[i].end()) continue;    //没找到跳过while(it!=v[i].end())   //找到则依次暴力查找{if(it->val==k.val){li=min(li,it->idx);ri=max(ri,it->idx);}elsebreak;it++;}}if(li==INF||ri==-INF) return -1;return ri-li;
}
int main()
{scanf("%d%d",&n,&q);{sz=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i].val);a[i].idx=i;pos[i]=(i-1)/sz+1;v[pos[i]].push_back(a[i]);}for(int i=1;i<=pos[n];i++) sort(v[i].begin(),v[i].end());for(int i=1;i<=q;i++){int flag,l,r,c;scanf("%d",&flag);if(flag==1){scanf("%d%d%d",&l,&r,&c);add(l,r,c);}if(flag==2){scanf("%d",&c);printf("%dn",query(c));}}}//system("pause");
}

P 为什么你这么熟练啊

这题目刚开始我看着感觉跟主席树一模一样，主席数刚好每个结点存这个数在l r区间出现的次数，然后加了点自以为是的小优化就交了光荣tle2，

看了题解是莫队，其实之前想到了莫队，但是没想到 l1 r1 l2 r2 这种有关联的区间怎么莫队。

结果被大佬折服了，l r x出现的次数其实是1到r x出现次数减去 1 到 l-1 出现的次数。

这样原式子就可以转换为（（1，r1）-（1，l1-1））*（（1，r2）-（1，l2-1）），化简之后为

（1，r1）*（1，r2）-（1，r1）*（1，l2-1）-（1，l1-1）*（1，r2）+（1，l1-1）*（1，l2-1）。

这样就可以把原查询分为4个区间查询来写，这样分开以后就可以使用莫队了，把每个答案相应的贡献计算清楚即可。

具体看代码有莫队基础应该很容易理解。

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=5e4+5;
const int INF=1e9+7;
int n,q,a[maxn],pos[maxn],sl[maxn],sr[maxn],ans[maxn];
struct node //sl数组表示L移动是sl中x出现的次数 sr同理
{int l,r,flag,idx;bool operator<(const node &p) const{if(pos[l]==pos[p.l]) return r<p.r;return pos[l]<pos[p.l];}
};
vector<node> v;
int main()
{scanf("%d",&n);int sz=sqrt(n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[i]=(i-1)/sz+1;scanf("%d",&q);for(int i=1;i<=q;i++){int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);  //按照推的式子分为4个区间v.push_back({r1,r2,1,i});v.push_back({r1,l2-1,-1,i});v.push_back({l1-1,r2,-1,i});v.push_back({l1-1,l2-1,1,i});}sort(v.begin(),v.end());int L=0,R=0,res=0;for(auto it=v.begin();it!&#d();it++){while(L>it->l)  //这里L要-- 因为是乘法 L--之前 答案会减去 sr中a[L]的次数{               //之后的四步都同理res-=sr[a[L]];sl[a[L]]--;L--;}while(L<it->l){L++;res+=sr[a[L]];sl[a[L]]++;}while(R>it->r){res-=sl[a[R]];sr[a[R]]--;R--;}while(R<it->r){R++;res+=sl[a[R]];sr[a[R]]++;}ans[it->idx]+=(it->flag*res);}for(int i=1;i<=q;i++)printf("%dn",ans[i]);//system("pause");
}

Q 这是一道简单题

真简单题没啥说的

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9+7;
ll ans,a[maxn];
int n,m;
struct node
{int l,r,mid;ll sum,lazy;
}t[maxn<<2];
void pushdown(int rt)
{if(t[rt].lazy!=0){t[lson].sum+=t[rt].lazy*(t[lson].r-t[lson].l+1);t[lson].lazy+=t[rt].lazy;t[rson].sum+=t[rt].lazy*(t[rson].r-t[rson].l+1);t[rson].lazy+=t[rt].lazy;t[rt].lazy=0;}
}
void pushup(int rt)
{t[rt].sum=t[lson].sum+t[rson].sum;
}
void build(int l,int r,int rt)
{int mid=(l+r)>>1;t[rt].l=l,t[rt].r=r;t[rt].mid=mid;if(l==r){t[rt].lazy=0;t[rt].sum=a[l];return ;}build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int l,int r,ll val,int rt)
{if(l<=t[rt].l&&t[rt].r<=r){t[rt].sum+=(val*(t[rt].r-t[rt].l+1));t[rt].lazy+=val;return ;}pushdown(rt);if(l<=t[rt].mid) update(l,r,val,lson);if(r>t[rt].mid) update(l,r,val,rson);pushup(rt);
}
ll query(int pos,int rt)
{ll res=0;if(t[rt].l==t[rt].r){return t[rt].sum;}pushdown(rt);if(pos<=t[rt].mid) res=query(pos,lson);if(pos>t[rt].mid) res=query(pos,rson);pushup(rt);return res;
}
int main()
{while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,n,1);for(int i=1;i<=n;i++){int flag,l,r;ll v;scanf("%d%d%d%lld",&flag,&l,&r,&v);if(flag) printf("%lldn",query(r,1));else update(l,r,v,1);}}//system("pause");
}

R letter Kingdom

不会做！！！

这次的训练题教练说是基础

太难了啊= =

不过起到了很好的智商恢复作用