双指针&前缀和

AcWing 799 最长连续不重复子序列

右端点扩展，出现重复时移动左端点。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<int> a(n); for(auto &x:a) cin >> x;
    unordered_map<int,int> cnt; int ans=0;
    for(int i=0,j=0;i<n;++i) { ++cnt[a[i]]; while(cnt[a[i]]>1) --cnt[a[j++]]; ans=max(ans,i-j+1); }
    cout << ans << '\n';
}

一维前缀和

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m; cin >> n >> m; vector<long long> s(n+1);
    for(int i=1;i<=n;++i) { long long x; cin >> x; s[i]=s[i-1]+x; }
    while(m--) { int l,r; cin >> l >> r; cout << s[r]-s[l-1] << '\n'; }
}

二维前缀和

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m,k; cin >> n >> m >> k; vector<vector<long long>> s(n+1,vector<long long>(m+1));
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { long long x; cin >> x; s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x; }
    while(k--) { int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] << '\n'; }
}

有序数组的两数之和

两个数组均须非递减，输出从 0 开始的下标。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m; long long x; cin >> n >> m >> x; vector<long long> a(n),b(m);
    for(auto &v:a) cin >> v; for(auto &v:b) cin >> v;
    for(int i=0,j=m-1;i<n && j>=0;++i) {
        while(j>=0 && a[i]+b[j]>x) --j;
        if(j>=0 && a[i]+b[j]==x) { cout << i << ' ' << j << '\n'; return 0; }
    }
}

A-B 数对

适用于 C>0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long c; cin >> n >> c; vector<long long> a(n); for(auto &x:a) cin >> x;
    sort(a.begin(),a.end()); long long ans=0;
    for(int i=0,l=0,r=0;i<n;++i) {
        while(l<n && a[l]<a[i]+c) ++l;
        while(r<n && a[r]<=a[i]+c) ++r;
        ans+=r-l;
    }
    cout << ans << '\n';
}

递增三元组

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<int> a(n),b(n),c(n);
    for(auto &x:a) cin >> x; for(auto &x:b) cin >> x; for(auto &x:c) cin >> x;
    sort(a.begin(),a.end()); sort(b.begin(),b.end()); sort(c.begin(),c.end());
    long long ans=0; int i=0,j=0;
    for(auto x:b) { while(i<n && a[i]<x) ++i; while(j<n && c[j]<=x) ++j; ans+=1LL*i*(n-j); }
    cout << ans << '\n';
}

两组钻石

排序后分成不相交的两组，每组最大值与最小值之差不超过 K。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k; cin >> n >> k; vector<int> a(n),left(n+1),right(n+1);
    for(auto &x:a) cin >> x; sort(a.begin(),a.end());
    for(int i=0,j=0;i<n;++i) { while(a[i]-a[j]>k) ++j; left[i+1]=max(left[i],i-j+1); }
    for(int i=n-1,j=n-1;i>=0;--i) { while(a[j]-a[i]>k) --j; right[i]=max(right[i+1],j-i+1); }
    int ans=0; for(int i=0;i<=n;++i) ans=max(ans,left[i]+right[i]); cout << ans << '\n';
}