前缀和和差分的思想

• 一，前缀思想
• 二，差分思想

• 新定义性： 可以对需要前缀和的条件和数目进行取舍if (...) a[i]= a[i-1] + ..
• 叠加性：在有序的数组标的前提下，二分就能取得第k大的数，注意和其他计数的结合
• 注意大数据范围
• 数学性： 求和求积运算的一切都可以实现

例一：

回文性质， 固定 A 的位置，找到前后有多少 Q ，乘法原理即可
找 Q 的过程就是新定义的典例

int n,ans;
string s;
int t[N];
int main()
{
    cin>>s;
    n= s.size();
    s = ' ' + s;
    for (int i = 1; i <= n; i ++ ) t[i]= t[i-1]+(s[i]=='Q');
    for (int i = 2; i < n; i ++ ) if(s[i]=='A')ans+= t[i-1]*(t[n]-t[i]);
    cout< 
二，差分思想 
作用持续： 单点修改的目的是在往后的数据上造成一个扰动，这个扰动只要没用被新的单点修改扰动抵消，在前缀（…）这种具有积累效应的运算上就会持续存在
作用形式：差分数组，懒标记，异或运算
 
具体而言：
 1，需要开始去区间 *** 做的地方在差分数组上打上（作用记号），作用形式不限，叠加效应不能忽视
 2，注销某一种 *** 作是，在差分数组上打上（注销记号），注销这种 *** 作
 
例一：（可能是个模拟？或者是降维）
 
 
差分套差分，跳水的影响具有周期波动和规律性，第一层差分表示影响范围，第二层表示具体影响度，初始均为0
 delta 人为处理偏移量，在数组下标下处理横坐标负数
 
#define rep(i,j,k) for(int i= j;i<=k;i++)
int c[N],s[N];
int n,m;
signed main()
{
    int delta = 1000000;
    scanf("%d%d",&m,&n);
    while (m--)
    {
        int v,x;
        scanf ("%d%d",&v,&x);
        c[x- 3*v+1 +delta]++;
        c[x- 2*v+1 +delta]-= 2;
        c[x +1 +delta]+= 2;
        c[x+ 2*v+1 +delta]-= 2;
        c[x+ 3*v+1 +delta]++;
    }

    rep(i,0,delta+n) c[i]+= c[i-1] , s[i]= s[i-1]+c[i];
    rep(i,delta+1,delta+n)printf("%d ",s[i]);
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5653211.html