树状数组2

之前写树状数组只写了了单点修改区间查询以及区间修改单点查询.今天因为一个题目要用到树状数组区间修改区间查询,所以先更一下区间修改以及区间查询.

• 区间修改以及区间查询呢,简单的来说区间修改还是和以前一样用一个D[i]数组单点修改即可完成.如何进行区间查询呢?这里我们用到两个数组即可完成,c1[i]表示d[i]的前缀和,c2[i]表示d[i]*(i-1)的前缀和.如此我们就可以进行区间修改以及区间查询了.c1,c2类似之前的sum数组.

https://www.luogu.com.cn/problem/P6477

直接看这个题,其实树状数组这种数据结构大多数只是一种降低时间复杂度的工具,题目的重点在于思维的过程
求不可重集的计数,大概就是推出相邻两项的关系,然后就知道了一个公式...然后就没了= - =因为不会打公式,啊,求和公式啥的都不会打..
这里的树状数组大概是维护的l区间嘛,然后扫描线的做法统计答案罗..(还是挺复杂的一个蓝题,其实我觉得跟紫题差不多...)
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e6+5;
ll a[N],n,c1[N],c2[N],last[N],d[N],ls[N];

ll lowbit(ll x)   {  return x&(-x); }

void add(ll pos,ll val)
{
    ll x=pos;
    while(pos<=n)
    {
        c1[pos]+=val;
        c2[pos]+=(x-1)*val;
        pos+=lowbit(pos);
    }
}

ll query(ll pos)
{
    ll res=0;ll x=pos;
    while(pos)
    {
        res+=x*c1[pos]-c2[pos];
        pos-=lowbit(pos);
    }
    return res;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)   {scanf("%lld",&a[i]);ls[i]=a[i];}
    sort(ls+1,ls+1+n);
    int cnt=unique(ls+1,ls+1+n)-ls-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(ls+1,ls+1+n,a[i])-ls;
        last[i]=d[a[i]];
        d[a[i]]=i;
    }
    ll ans=0,now=0;
    for(int i=1;i<=n;i++)
    {
        now+=2ll*(query(i)-query(last[i]))+i-last[i];
        now%=mod;
        ans+=now;
        ans%=mod;
        add(last[i]+1,1);
        add(i+1,-1);
    }
    printf("%lld\n",ans);
    return 0;
}