題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長度為 $n$ 的數(shù)列，和一個(gè)數(shù)字 $k$。現(xiàn)在給出 $m$ 次詢問，每次查詢需要回答區(qū)間 $[l,r]$ 內(nèi)有多少個(gè)子區(qū)間，滿足區(qū)間內(nèi)不同的數(shù)字個(gè)數(shù)大于等于 $k$

題目分析：一開始看到強(qiáng)制在線和區(qū)間問題以為是主席樹，后來發(fā)現(xiàn) $k$ 自始至終都是不變的。這樣每個(gè)點(diǎn)作為左端點(diǎn)時(shí)，假設(shè)某個(gè)點(diǎn)可以作為右端點(diǎn) $r$ 與其對應(yīng)，那么顯然當(dāng) $i\in [r+1,n]$ 的 $i$ 作為右端點(diǎn)時(shí)，區(qū)間 $[l,i]$ 同樣也是滿足條件的

所以我們只需要預(yù)處理出對于每個(gè)點(diǎn)作為左端點(diǎn) $l$ 時(shí)，可以匹配的下標(biāo)最小的右端點(diǎn) $r$ 即可，這里我記為 $b_i$，數(shù)組 $b$ 不難看出可以直接用尺取來求，這里不多贅述了

那么考慮對于每次詢問 $[l,r]$ ，答案顯然就是 ${\sum }_{i=l}^{r}max(0,r?b_i+1)$

然后就需要發(fā)現(xiàn)數(shù)組 $b$ 的一個(gè)小性質(zhì)，那就是數(shù)組 $b$ 是單調(diào)不減的，所以對于上述求和公式就可以找到一個(gè)分界點(diǎn) $pos$。有 $i\in [l,pos]$ 時(shí)，滿足 $r?b_i+1>=0$；同理 $i\in [pos+1,r]$ 時(shí)，滿足 $r?b_i+1<0$，這樣一來 $[pos+1,r]$ 的貢獻(xiàn)就可以忽略不計(jì)了

到此為止只需要將上述求和公式拆一下就可以輕松實(shí)現(xiàn)了：
${\sum }_{i=l}^{r}max(0,r?b_i+1)={\sum }_{i=l}^{pos}{b}_i+(r+1)?(pos?l+1)$

代碼：

// Problem: Alice and Bob // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/17148/C // Memory Limit: 1048576 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int a[N],b[N]; LL sum[N]; map<int,int>mp; LL get_sum(int l,int r) {return sum[r]-sum[l-1]; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m,k;read(n),read(m),read(k);for(int i=1;i<=n;i++) {read(a[i]);}int r=0,cnt=0;for(int i=1;i<=n;i++) {while(cnt<k&&r<=n) {r++;mp[a[r]]++;if(mp[a[r]]==1) {cnt++;}}if(cnt>=k) {b[i]=r;} else {b[i]=n+1;}sum[i]=sum[i-1]+b[i];mp[a[i]]--;if(mp[a[i]]==0) {cnt--;}}LL ans=0;while(m--) {LL l,r;read(l),read(r);l=(l^ans)+1;r=(r^ans)+1;if(l>r) {swap(l,r);}int ll=l,rr=r,pos=-1;while(ll<=rr) {int mid=(ll+rr)>>1;if(0<=r-b[mid]+1) {pos=mid;ll=mid+1;} else {rr=mid-1;}}if(pos==-1) {puts("0");ans=0;} else {LL ans1=1LL*(r+1)*(pos-l+1);LL ans2=get_sum(l,pos);printf("%lld\n",ans=ans1-ans2);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客 - Alice and Bob(尺取+二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。