模版

int l = 1, r = 1;
while(l <= r && l <= n){
  	while(r <= n && ){//右指针右移
      	++r;
    }
  	if(){
      	//符合条件的话就更新ans
      	//注意，符合的区间是[l, r - 1]!!!
    }
  	++l;
  	//指针左移，并需要消除最左端指针的影响
}

Subsequence

题目描述：

求一个子区间的数字和大于等于m的区间长度的最小值

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    int l = 1, r = 1;
    ll sum = 0;
    int ans = inf;
    while(l <= r && l <= n){
        while(r <= n && sum <= m){
            sum += tr[r++];
        }
        // cout<<l<<' '<<r - 1<<' '<<sum<<endl;
        if(sum >= m)ans = min(ans, r - l);
        sum -= tr[l++];
    }
    if(ans == inf)cout<<0<<endl;
    else cout<<ans<<endl;
}

洛谷 p1638 逛画展

题目描述：

求刚好拥有所有m种数字的最短区间.

int tr[MAX];
int num[MAX];
set<int>se;
void work(){
    cin>>n>>m;
    rep(i, 1, n)cin>>tr[i];
    int l = 1, r = 1;
    int ans = inf;
    while (l <= r && l <= n) {
        while (se.size() != m && r <= n) {//如果不同的数字的数量小于m，右移指针
            if(!se.count(tr[r])){//判断这个数字有没有出现过，没有的话就扔进set
                se.insert(tr[r]);
            }
            ++num[tr[r++]];//让这个数的数量+1
        }
        if(se.size() < m)break;//如果数的数量小于m就跳出
        if(ans > r - l + 1){//更新答案
            ans = r - l + 1;
            a = l;b = r - 1;
        }
        if(num[tr[l]] == 1)se.erase(tr[l]);//判断是否需要将这个数移除set
        --num[tr[l++]];
    }
    cout<<a<<' '<<b<<endl;
}

Unique Snowflakes

题目描述：

求没有重复数字的最长区间.

void work(){
    cin >> n;
    rep(i, 1, n)cin >> tr[i];
    int l = 1, r = 1;
    set<int>se;
    int ans = 1;
    while (l <= r) {
        while (!se.count(tr[r]) && r <= n) {//判断能不能塞进这个数
            se.insert(tr[r++]);
        }
        ans = max(ans, r - l);
        se.erase(tr[l++]);
    }
    cout << ans <<endl;
}

Atcoder 4142 Xor Sum 2

题目描述：

求区间[l,r]的对数,使得A[l] xor A[l+1] xor … xor A[r] = A[l] + A[l+1] + … +A[r].

思路：

非常妙的一个题

我们要知道一个事情，就是a ^ b =a + b的条件是a&b=0，也就是转换成二进制后每一位必须不一样，这样异或才能是相加的效果

那区间值异或后等于这个区间的和的条件就是二进制下每位必须只有一个数是1

接下来就可以利用尺取法，sum表示这个区间的和，判断能不能让指针右移的方法是判断sum & tr[r] == 0，消除左指针的方法也很简单，sum -= tr[l]，因为这个区间是符合条件的，异或等于加，那取消异或影响就等于减去值

ll tr[MAX];
void work(){
    cin>>n;
    rep(i, 1, n)cin>>tr[i];
    int l = 1, r = 1;
    ll sum = 0;
    ll ans = 0;
    while (l <= r && l <= n) {
        while (!(sum & tr[r]) && r <= n) {
            sum += tr[r++];
        }
        ans += r - l;
        sum -= tr[l++];
    }
    cout<<ans<<endl;
}

还有一些题，懒得写了，下次再补