牛客競賽資料結構專題班樹狀陣列、線段樹練習題
筆者蒟蒻能力有限，能寫幾道寫幾道
[NOIP2012]借教室
顯然很符合線段樹的操作，但是是區間和，還是區間最小值，還是區間最大值需要甄選
簡化題意：求第幾個操作后區間出現小于等于0，先輸出-1，再輸出第幾個操作，如果操作完后都大于0，那么輸出0
通過題意可以果斷排除區間和和區間最大值，只需要維護區間最小值即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstring>
using namespace std;
#define int long long
int n,m;const int maxn=1e6+10;
int a[maxn];
int ans[maxn<<2],laz[maxn<<2];
int read(){
int x=0,f=1;
char ch=getchar();
while(ch>'9' || ch<'0') if(ch=='-') f=-1;else ch=getchar();
while(ch<='9' && ch>='0') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void push_up(int p){
ans[p]=min(ans[p<<1],ans[p<<1|1]);
}
void build(int p,int l,int r){
if(l==r){
ans[p]=a[l];
return ;
}int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
void change(int p,int pf,int l,int r){
ans[p]-=laz[pf];
laz[p]+=laz[pf];
}
void push_down(int p,int l,int r){
int mid=(l+r)>>1;
change(p<<1,p,l,mid);
change(p<<1|1,p,mid+1,r);
laz[p]=0;
}
void update(int p,int l,int r,int nl,int nr,int k){
if(nl<=l && r<=nr){
ans[p]-=k;
laz[p]+=k;return ;
}
push_down(p,l,r);
int mid=(l+r)>>1;
if(nl<=mid) update(p<<1,l,mid,nl,nr,k);
if(nr>mid) update(p<<1|1,mid+1,r,nl,nr,k);
push_up(p);
return ;
}
bool query(int p,int l,int r,int nl,int nr){
if(nl<=l && r<=nr) return ans[p]<0;
int mid=(l+r)>>1;
push_down(p,l,r);
bool book=0;
if(nl<=mid) book|=query(p<<1,l,mid,nl,nr);
if(nr>mid) book|=query(p<<1|1,mid+1,r,nl,nr);
return book;
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;++i) a[i]=read();
build(1,1,n);int book=0;
for(int i=1;i<=m;++i){
int k=read(),nl=read(),nr=read();
if(book) continue;
update(1,1,n,nl,nr,k);
if(query(1,1,n,nl,nr)){
puts("-1");
printf("%d\n",i);book=i;
}
}
if(!book) puts("0");
return 0;
}
[SDOI2009]HH的項鏈
也是區間操作，統計的是區間內有多少個不同的數
其實很容易想到定義一個sum[i]表示前i個數中有多少個不同的數
那么答案易得 \(ans=sum[r]-sum[l-1]\)
沒有要求在線處理，那么這種題可以考慮在線或離線處理
可以考慮離線做法，一般離線做法都會考慮對詢問序列進行一系列的操作
怎么操作等下說
我們先來研究題面
舉例
\(1,2,3,4,5,3,6\)
可以很直觀的看出來\(sum[]={0，1，2，3，4，5，5，6}\)
當查詢區間為[5,6]時，ans=sum[6]-sum[5-1]=1,顯然不對
那又是什么原因造成這種錯誤，易發現[5,6]中只有3，5兩個數字
sum[6]代表前6個數中共有5種數，sum[4]代表前4個數中有4種數，
好像沒毛病
sum[6]-sum[4]，減去是兩個區間內共有的數的種數，但是帶入原序列中會發現我們減去3這個數，但[5,6]中卻有這個數
所以當遇到所求區間5,6和減去區間[1,4]（即sum[4]）出現共同的數的時候不可這么做
為賦予原有的意義
所以我們進行sum[6]-sum[4]之前，sum[4]應該減去[4,6]中的共有的數的種數，sum[4]-1=3,而此時sum[6]-sum[4]=2
歸納上述程序
查詢某個區間[l,r]時，我們設[1,l-1]中的有x種數與[l,r]中的數相同，\(sum[r]-(sum[l-1]-x)=ans\)，如果x=0，說明沒有出現重復的共同數
我們討論完單個重復情況
如果有多個重復情況了？（其實也可以再手動模擬下出現兩種數相同的情況）
受到單個情況討論的啟發，我們可以將按r進行排序，然后，從上一個r'列舉到目前這個r，如果遇到個數之前出現過\(sum[p]=sum[p]-1\)(p為上次這個數出現的位置)
列舉到這個r之后重新記錄這個數的位置，然后ans=sum[r]-sum[l-1]
實作時略有不同
你會發現sum[]是動態變化的，所以用樹狀陣列即時求出sum[r]和sum[l-1]即可
然后sum[p]=sum[p]-1（add(p,-1)），會影響后面的數求和，所以sum[p']（p'為另一個與它相同的卻在它后面的數）(add(p',1))
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define lowbit(x) x&-x;
int n,m;
const int maxn=1e6+10;
int t[maxn],a[maxn];
int pre[maxn];//記錄某個數上次出現的位置
int ans[maxn];
struct node{
int l,r,p;
}ask[maxn];
int read(){
int x=0;char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
bool cmp(node a,node b){
return a.r<b.r;
}
void add(int x,int val){//加上val
while(x<=n){
t[x]+=val;
x+=lowbit(x);
}
}
int sum(int x){//求1~x和
int res=0;
while(x){
res+=t[x];
x-=lowbit(x);
}return res;
}
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
m=read();
for(int i=1;i<=m;++i) ask[i].l=read(),ask[i].r=read(),ask[i].p=i;//讀入
sort(ask+1,ask+1+m,cmp);//按r排序
int nex=1;
for(int i=1;i<=m;++i){
for(int j=nex;j<=ask[i].r;++j){
if(pre[a[j]]) add(pre[a[j]],-1);//這個數之前出現過，減去
add(j,1);//重新計算
pre[a[j]]=j;//記錄這個數最近出現的位置
}
nex=ask[i].r+1;//更新為當前這個r的下一位
ans[ask[i].p]=sum(ask[i].r)-sum(ask[i].l-1);//這個詢問的答案
}
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
return 0;
}
'ZFY AK IOI'
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296236.html
標籤：其他