开个帖记录 2019-09-01之后接触到的线段树类型题
2019-09-08
XKC's basketball team
题目链接：https://nanti.jisuanke.com/t/41387
题意：
给你n个数字，寻找第i个数字后面比i大至少m且距离i最远的数字
分析：
线段树维护区间最大 , 然后从右区间开始搜寻
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<map> #define mm(a,n) memset(a, n, sizeof(a)) using namespace std; #define ll long long template <class T> void read(T &x) { x = 0; char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); } const int N=5e5+5; struct node { int l,r,MAX; }tree[N<<2]; int n,m; int a[N]; void build(int i,int l,int r) { tree[i].l=l,tree[i].r=r; if(l==r) { scanf("%d",&tree[i].MAX); a[l]=tree[i].MAX; return ; } int mid=l+r>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); tree[i].MAX=max(tree[i<<1].MAX,tree[i<<1|1].MAX); } int query(int i,int l,int r,int v) { if(tree[i].l==tree[i].r) return tree[i].l; int mid=tree[i].l+tree[i].r>>1; if(tree[i<<1|1].MAX>=v) return query(i<<1|1,l,r,v); else if(l<=mid&&tree[i<<1].MAX>=v) return query(i<<1,l,r,v); else return -1; } int main() { ios::sync_with_stdio(false); read(n);read(m); build(1,1,n); int ans; for(int i=1;i<=n;i++) { if(i==n) ans=-1; else ans=query(1,i+1,n,a[i]+m); if(ans!=-1) ans-=i+1; if(i == n) cout<<ans<<endl; else cout<<ans<<" "; } return 0; }
2019-10-03
D. Distinct Characters Queries
题目链接：https://codeforces.com/contest/1234/problem/D
题意：给你一个字符串 ， 有q个操作：
①、 将 pos 位置的字符改为 c
②、查询 L~ R 区间不同字符的个数
分析：
挺水的一题。因为全是小写字符 , 所以我们可以对每个单独字符开个线段树, 那么一共就开了26个线段树 ,然后预处理：将母串中第 i 个位置的字符对应的线段树的第 i 个区间的值 + 1。
那么当操作为 ① 的时候我们只要将母串pos位置的字符对应线段树的pos区间值 -1 , 然后c字符对应线段树的pos区间 +1
当操作为 ②的时候我们只要判断每个字符是否有出现在L ~ R区间 , 即遍历 26 颗线段树 L ~ R 的区间和是否为 0 .若不为 0 , ans++ , 遍历完后输出ans即可
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define INF 0x3f3f3f3f #define sz(x) ((int)x.size()) #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res) { bool flag=false; char ch; while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm; isdigit(ch=getchar()); res=(res<<1)+(res<<3)+numm); flag&&(res=-res); } template<typename T>void Out(T x) { if(x<0)putchar('-'),x=-x; if(x>9)Out(x/10); putchar(x%10+'0'); } ll pow_mod(ll x, ll n , ll mod) { ll res=1; while(n) { if(n&1)res=res*x%mod; x=x*x%mod; n>>=1; } return res; } #define lson l,mid,rt << 1 #define rson mid + 1,r,rt << 1 | 1 #define ll long long using namespace std; const int N = 4e5 + 5000; const ll mod = 1e9 + 7; ll n,k; ll a[N]; int t[N][26]; void update(int l,int r,int rt,int id,int k,int val) { if(k < l || k > r) return ; if(l == r) { t[rt][id] += val; return ; } int mid = l + r >> 1; if(k <= mid) update(lson,id,k,val); else update(rson,id,k,val); t[rt][id] = t[rt << 1][id] + t[rt << 1 | 1][id]; } int qu(int l,int r,int rt,int ql,int qr,int id) { if(r < ql || l > qr) return 0; int res = 0; if(ql <= l && qr >= r) return t[rt][id]; int mid = l + r >> 1; if(ql <= mid) res += qu(lson,ql,qr,id); if(qr > mid) res += qu(rson,ql,qr,id); return res; } int main() { string str = " "; string strr; cin >> strr; str += strr; n = sz(strr); rep(i ,1 ,n) { update(1,n,1,str[i] - 'a',i,1); } int q,op,l,r; sd(q); while(q--) { sd(op); if(op == 1) { int pos; char c; sd(pos); cin >> c; update(1,n,1,str[pos] - 'a',pos ,-1); str[pos] = c; update(1,n,1,c - 'a',pos,1); } else { sdd(l , r); ll ans = 0; rep(i,0,25) { if(0 < (qu(1,n,1,l,r,i))) ans++; } pd(ans); } } return 0; }
2019-10-06
The Child and Sequence
题目链接：https://codeforces.com/contest/438/problem/D
题意：
有n个数、m条指令 , 指令对应的操作分别是：
①、区间求和
②、区间取模
③、单点修改
根据指令完成操作
分析：
很明显这题就是要求维护一棵支持区间取膜，单点更新，区间求和的线段树。区间求和 和 单点修改都没什么问题，问题就在区间取模
先将区间和求出来再取模这是肯定不行的 , 所以我们需要换种思想——对于一个区间，如果它的区间和 sum < Mod ， 那我们对整个区间取模就没有意义了 , 这是个剪枝的条件
所以我们可以先进行单点更新 , 知道区间和 sum < Mod , 那么我们就没有对它进行取模的必要了。 再者对于每个数取模一个小于它的数 , 它的值肯定会小于原来的二分之一
当搜寻到某个区间和小于 Mod 的时候 , 我们就可以直接停止搜索 , 这样算下来时间复杂度并不会很高 ， 也就能做了。
详见代码
View Code
2019-10-08
Max answer
题目链接：https://nanti.jisuanke.com/t/38228
题意：
给一个长为n(n <= 500000)的数组a, 对每个区间，求区间和乘区间最小值的最大值(−1e5 ≤ ai ≤1e5).
分析：
这道题乍一看像是单调栈的模板题 , 但很可惜的是 ai 的取值可以为负数 , 所以对于以 ai 为最小值的区间 , 若 ai 为负数 , 要找到最小区间和 , 若为 ai 为正数 , 要找到最大区间和
对于正数ai，利用单调栈寻找以ai为最小值的区间，利用前缀和数组求区间和再*ai 即结果（ai 为正数 , ai为区间最小值）
先用单调栈求出以a[i]为最小值能够延伸的左端点L[i]和右端点R[i] , 然后对于每个正数，我们用该数乘以这个区间和。区间和用前缀和来求，对于每个数所能影响的最大区间我们已经求出来了。对于负数来说，我们需要求在它右区间的最小前缀和减去左区间的最大前缀和 , 因为只有它的区间和最小对应的这个区间的value值才最大，又由区间和=sum[j]-sum[i]可知，sum[j]最小，sum[i]最大时才能时这个区间和最小，所以问题的关键转化为寻找最小的sum[j]和最大的sum[i]
对于右区间的最小前缀和，以及左区间的最大前缀和我们用线段树来求
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} const int N = 5e5 + 10; ll sum[N],a[N]; ll maxn[N << 2],minn[N << 2]; void build(int l,int r,int root) { if(l==r) { maxn[root]=minn[root]=sum[l]; return ; } int mid=l+r>>1; build(l,mid,root<<1); build(mid+1,r,root<<1|1); maxn[root]=max(maxn[root<<1],maxn[root<<1|1]); minn[root]=min(minn[root<<1],minn[root<<1|1]); } ll qmax(int l,int r,int root,int ql,int qr) { if(l>=ql&&r<=qr) return maxn[root]; int mid=l+r>>1; ll ans=-INF; if(mid>=ql) ans=qmax(l,mid,root<<1,ql,qr); if(mid<qr) ans=max(ans,qmax(mid+1,r,root<<1|1,ql,qr)); return ans; } ll qmin(int l,int r,int root,int ql,int qr) { if(l>=ql&&r<=qr) return minn[root]; int mid=l+r>>1; ll ans=INF; if(mid>=ql) ans=qmin(l,mid,root<<1,ql,qr); if(mid<qr) ans=min(ans,qmin(mid+1,r,root<<1|1,ql,qr)); return ans; } int LL[N],RR[N],st[N]; int main() { ios; int n; cin >> n; rep(i ,1 ,n) cin >> a[i],sum[i] = sum[i-1]+a[i]; build(1,n,1); int top=0; rep(i ,1 ,n) { while(top&&a[st[top]]>a[i]) RR[st[top--]]=i-1; st[++top]=i; } while(top) RR[st[top--]]=n; for(int i=n;i>=1;i--) { while(top&&a[st[top]]>a[i]) LL[st[top--]]=i+1; st[++top]=i; } while(top) LL[st[top--]]=1; ll ans = -INF; rep(i ,1 ,n) { if(a[i]>0) ans=max(ans,a[i]*(sum[RR[i]]-sum[LL[i]-1])); else ans=max( ans,a[i]*( qmin(1,n,1,i,RR[i])-qmax(1,n,1,LL[i],i)) ); } cout << ans << endl; return 0; }
2019-10-08
Platforms Jumping
题目链接：https://codeforces.com/contest/1256/problem/C
题意：
有一条宽为 n + 1 的桥 ， 你的初始位置在 0 ，每次你可以跳跃 1 ~ d 的宽度 。同时你有 m 块木板 ， 这 m 块木板可以任意移动，但它们的相对位置是不能变的。
若改变木板的位置可以跳至 n + 1 的位置，则输出 YES 和 m 块木板的摆放位置，否则输出NO
分析：
因为 m 块木板必须都使用到 ， 所以我们可以先将所有木板堆积在末尾，然后用now标记当前位置 ，tot 记录未被使用的木板的最靠前的位置。因为未使用的木板一定是从头一路连接到n + 1的位置（中间没有空隙），所以当 now + d >= tot 的时候，剩下没用到的木板保持堆积在末尾的状态就可以了
区间用线段树维护即可 ， 代码还是很好懂的
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); const int inf (0x3f3f3f3f); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;} ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;} bool CH(ll a,ll n,ll x,ll t) {ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL)); ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;} int prime[30000010],minprime[30000010]; void euler(int n) {int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++) {minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}} const int N = 5e5 + 10; struct node{ int id , c , l , r; }a[N]; int ans[N]; int tree[N << 2] , lz[N << 2]; void build(int node,int l,int r){ if(l == r){ cin >> tree[node]; return; } int mid = (l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); tree[node] = tree[node*2] + tree[node*2 + 1]; } void update(int n,int index,int l,int r,int node){ if(l == r) { tree[node] = n; return; } int mid = (l+r) / 2; if(index <= mid){ update(n,index,l,mid,node*2); }else{ update(n,index,mid+1,r,node*2+1); } tree[node] = tree[node*2] + tree[node*2 + 1]; } void push_down(int node,int l,int r){ if(lz[node]){ int mid = (l+r) / 2; lz[node*2] += lz[node]; lz[node*2 + 1] += lz[node]; tree[node*2] += 1LL*(mid - l + 1)*lz[node]; tree[node*2 + 1] += 1LL*(r - mid)*lz[node]; lz[node] = 0; } } void update_range(int node,int l,int r,int L,int R,int add){ if(l <= L && r >= R){ lz[node] += 1LL*add; tree[node] += 1LL*(R - L + 1)*add; return; } push_down(node,L,R); int mid = (L+R) / 2; if(mid >= l) update_range(node*2,l,r,L,mid,add); if(mid < r) update_range(node*2 + 1,l,r,mid+1,R,add); tree[node] = tree[node*2] + tree[node*2 + 1]; } ll query_range(int node,int L,int R,int l,int r){ if(l <= L && r >= R) return tree[node]; push_down(node,L,R); int mid = (L+R) / 2; ll sum = 0; if(mid >= l) sum += query_range(node*2,L,mid,l,r); if(mid < r) sum += query_range(node*2 + 1,mid+1,R,l,r); return sum; } int main() { ios; int n , m , d ; cin >> n >> m >> d; int tot = n + 1 , sum = 0; rep(i , 1 , m) cin >> a[i].c , a[i].id = i , sum += a[i].c , tot -= a[i].c; if(sum + (m + 1) * d - m < n + 1) { cout << "NO" << ' '; return 0; } int last = n; per(i , m , 1) { a[i].r = last; a[i].l = last - a[i].c + 1; update_range(1 , last - a[i].c + 1, last , 1 , n , a[i].id); last -= a[i].c; } int now = 0; int k = 1 , flag = 0; while(k <= m) { if(now + d < tot) { update_range(1 , a[k].l , a[k].r , 1 , n , -a[k].id); update_range(1 , now + d , now + d + a[k].c - 1 , 1 , n , a[k].id); tot += a[k].c; now += d + a[k].c - 1; k ++ ; } else { break; } } cout << "YES" << ' '; rep(i , 1 , n) cout << query_range(1 , 1 , n , i , i) << " "; return 0; }