当前位置： 移动技术网 > 移动技术>移动开发>IOS > 莫队模板

莫队模板

2020年07月14日  | 移动技术网移动技术  | 我要评论 
#include <iostream>
#include <cstdio>
#include <stack>
#include <sstream>
#include <vector>
#include <map>
#include <cstring>
#include <deque>
#include <cmath>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <set>
#define mid ((l + r) >> 1) 
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define _for(i,a,b) for( int i = (a); i < (b); ++i)
#define _rep(i,a,b) for( int i = (a); i <= (b); ++i)
#define for_(i,a,b) for( int i = (a); i >= (b); -- i)
#define rep_(i,a,b) for( int i = (a); i > (b); -- i)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define hash Hash
#define next Next
#define count Count
#define pb push_back
#define f first
#define s second
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
const double eps = 1e-10;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) 
{
    read(first);
    read(args...);
}
ll res = 0;
ll ans[N];
struct node
{//按照l左端点所在的块来分，如果同一块按照r来排序
    int l, r , id, pos;
    bool operator < (const node & a) {
        if(pos == a.pos)  return r < a.r;
        else return pos < a.pos;
    }
}a[N];
int e[N];
ll cnt[N];
inline void Add(int n)
{
    n = e[n];
    cnt[n] ++;
    res += (cnt[n] * cnt[n]) - (cnt[n] - 1) * (cnt[n] - 1);
}
inline void Sub(int n)
{
    n = e[n];
    cnt[n] --;
    res -= (cnt[n] + 1) * (cnt[n] + 1) - cnt[n] * cnt[n];
}
int main()
{
    int n, m, k;
    read(n,m,k);
    for(int i = 1; i <= n; ++ i) read(e[i]);
    int block = sqrt(n);
    for(int i = 1; i <= m; ++ i)
    {
        int l, r;
        read(l,r);
        a[i] = {l,r,i,(l - 1) / block + 1};//分块
    }
    
    sort(a+1,a+m+1);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++ i)
    {
       while(a[i].l < l) Add(-- l);
       while(a[i].r > r) Add(++ r);
       while(a[i].l > l) Sub(l ++);
       while(a[i].r < r) Sub(r --);
       ans[a[i].id] = res;
    }
    for(int i = 1; i <= m; ++ i)
      cout << ans[i] << endl;
    return 0;
}

本文地址：https://blog.csdn.net/weixin_45630722/article/details/107283646

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网