1.AT_dp_w Intervals

我的博客

2.CF377D Developing Games

我的博客

這兩道題是比較經典的線段樹區間 trick，希望自己可以在以后的比賽中手切。

3.洛谷 P10814 離線二維數點

題意

給你一個長為 $n$ 的序列 $a$，有 $m$ 次詢問，每次詢問給定 $l,r,x$，求 $[l,r]$ 區間中小于等于 $x$ 的元素個數。

$1\le n,m,a_i,l,r,x\le 2\times 10^6$。

思路

前綴和思想，用 $[1,r]$ 中小于等于 $x$ 的數量，減去 $[1,l?1]$ 中小于等于 $x$ 的數量，就可以了。

考慮枚舉條件端點，從而改變權值。

用線段樹常數比較大，在洛谷 TLE 最后一個點，還是用樹狀數組吧，反正也比較方便。

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
inline void write(ll x)
{ if(x==0){putchar('0');return;}ll len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}
#define ls u<<1
#define rs u<<1|1
const ll N=2e6+9;
ll n,m,a[N];
ll M,ans[N];
struct term
{ll d,id,v;
};
vector<term>p[N];
struct BT
{ll T[N];ll lowbit(ll x){return x&(-x);}void add(ll x,ll k){for(int i=x;i<=M;i+=lowbit(i))T[i]+=k;}ll query(ll x){ll ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=T[i];return ret;}
}B;
int main()
{n=read(),m=read();for(int i=1;i<=n;i++){a[i]=read();M=max(M,a[i]);}for(int i=1;i<=m;i++){ll l,r,d;l=read(),r=read(),d=read();p[l-1].push_back((term){d,i,-1});p[r].push_back((term){d,i,1});M=max(M,d);}for(int i=1;i<=n;i++){B.add(a[i],1);for(auto x:p[i])ans[x.id]+=x.v*B.query(x.d);}for(int i=1;i<=m;i++)write(ans[i]),puts("");return 0;
}

4.洛谷 P1972 SDOI2009 HH的項鏈

給定一個序列 $a_i$，$m$ 次詢問區間 $[l,r]$ 中有多少種不同的數。

$1\le n,m,?a_i\le 10^6$，$1\le l\le r\le n$。

思路

一眼想用莫隊，但是 $\Theta (n\sqrt{n})$，令人畏懼（在古早時期學莫隊的時候卡常過了），那么分塊也并非正解了。

區間內有不同的數，那么多次出現的只算做一個。這題還是查詢區間，那么能不能用二維數點來做呢？

設序列中 $a_i$ 上一次出現在下標 $pr{e}_i$，沒有則 $pr{e}_i=0$，如果一個數在下標區間 $[l,r]$ 中首次出現，那么 $po{s}_i<l$；如果出現第二次，那么必然 $pr{e}_i\in [l,r]$。

那么題目就轉化成了，求區間 $[l,r]$ 中，有多少個 $pr{e}_i<l$。

那不就和上一題一樣了嗎？同樣使用前綴和思想，枚舉右端點。

不過這一題有 $0$ 出現，扔上樹狀數組會出問題，所以記得加 $1$。

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9;
ll n,m,a[N];
ll pre[N],pos[N];
ll ans[N];
struct que
{ll l,r,id;
}q[N];
bool cmp(que x,que y)
{if(x.l!=y.l)return x.l<y.l;return x.r<y.r;
}
struct term
{ll d,id,v;
};
vector<term>p[N];
struct BT
{ll T[N];ll lowbit(ll x){return x&(-x);}void add(ll x,ll k){for(int i=x;i<=n;i+=lowbit(i))T[i]+=k;}ll query(ll x){ll ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=T[i];return ret;}
}B;
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);pre[i]=pos[a[i]];pos[a[i]]=i;}scanf("%lld",&m);for(int i=1;i<=m;i++){ll l,r;scanf("%lld%lld",&l,&r);q[i]=(que){l,r,i};p[l-1].push_back((term){l-1,i,-1});p[r].push_back((term){l-1,i,1});}sort(q+1,q+m+1,cmp);//答案就是[l,r]中pre(i)<l的個數 for(int i=1;i<=n;i++){B.add(pre[i]+1,1);for(auto x:p[i])ans[x.id]+=x.v*B.query(x.d+1);}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;
}