双指针(9/1 and9/2 )

daimazhishen / 2023-09-02 / 原文

1、复习了前缀和，差分（一维和二维）

2、双指针

//双指针核心思想就是优化时间 for() for()->O(n^2)--->优化成O(n)
/*for(i=0,j=0;i<n;i++) 
{
  while(j<i&&check(i,j)) j++;
  //每道题的逻辑        
}*/
#include <iostream>

using namespace std;

const int N=1e5+10;

int a[N],b[N]={0};

int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int ret=0;
    for(int i=0,j=0;i<n;i++)
    {
        b[a[i]]++;
        while(j<i&&b[a[i]]>1) b[a[j++]]--;
        ret=max(ret,i-j+1);
    }
cout<<ret;
    return 0;
}

二、位运算

n的二进制表示中第k位是几

（1）把第k位移到最后一位 n>>k;

（2）看个位是几 x&1

（1）and（2）n>>k&1

三、离散化

1、for (auto item : query）遍历容器的新写法加上头文件 algorithm;

2、typedef pair<int, int> PII; 类似于定义结构体；提取其中元素 .first .second;

3、

802. 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是

现在，我们首先进行

接下来，进行

输入格式

第一行包含两个整数

接下来

再接下来

输出格式

共

数据范围

输入样例：

输出样例：

8
0
5

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;//存入下标容器
vector<PII> add, query;//add增加容器，存入对应下标和增加的值的大小
//query存入需要计算下标区间和的容器
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)//查找大于等于x的最小的值的下标
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;//因为使用前缀和，其下标要+1可以不考虑边界问题
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});//存入下标即对应的数值c

        alls.push_back(x);//存入数组下标x=add.first
    }

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});//存入要求的区间

        alls.push_back(l);//存入区间左右下标
        alls.push_back(r);
    }

    // 区间去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理插入
    for (auto item : add)
    {
        int x = find(item.first);//将add容器的add.secend值存入数组a[]当中，
        a[x] += item.second;//在去重之后的下标集合alls内寻找对应的下标并添加数值
    }

    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];

    // 处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);//在下标容器中查找对应的左右两端[l~r]下标，然后通过下标得到前缀和相减再得到区间a[l~r]的和
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}