2018-04-03 查漏补缺

优雅的暴力-莫队
莫队专题

A 区间不同个数的多少

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1000005
int n,m;
struct Node{
int a;int b;
int id;
}node[N];
int num[N];
int block;
bool cmp(struct Node a,struct Node b){

   if((a.a/block)==(b.a/block)){
    return a.b<b.b;
    }
return (a.a/block)<(b.a/block);
}
int ans[N];
int vis[N];
int main()
{

   scanf("%d",&n);
   for(int i=1;i<=n;i++){
    scanf("%d",&num[i]);
   }
   scanf("%d",&m);

   block=sqrt(n+0.5);
   for(int i=1;i<=m;i++){
    scanf("%d%d",&node[i].a,&node[i].b);
    node[i].id=i;
   }

 
   sort(node+1,node+1+m,cmp);

   int l,r;
   l=1;r=0;

   int t=0;
   for(int i=1;i<=m;i++){

   while(l<node[i].a){

        vis[num[l]]--;
        if(vis[num[l]]==0)
            t--;
        l++;
    }
    while(l>node[i].a){
            l--;

        vis[num[l]]++;
        if(vis[num[l]]==1)
            t++;
    }

     while(r<node[i].b){
             r++;
        vis[num[r]]++;
        if(vis[num[r]]==1)
            t++;

    }
    while(r>node[i].b){
        vis[num[r]]--;
        if(vis[num[r]]==0)
            t--;
        r--;
    }
    ans[node[i].id]=t;
   }
   for(int i=1;i<=m;i++){

        printf("%d\n",ans[i]);

   }

    return 0;
}

C

因为没有快速读入 超时了。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
#define N 1000005
typedef long long ll;
struct Node{
int a,b,k,id;}node[N];
vector<int>v[N];
int n,m;
int num[N];
int cn[N];
int en[N];
int block;
int c[N];
int mun[N];
int po[N];
int nn=1;
bool vis[N];
int nnum[N];
void add(int x){
   cn[mun[x]]++;
   c[cn[mun[x]]]++;
}
void del(int x){
    c[cn[mun[x]]]--;
    cn[mun[x]]--;
}
bool cmp(struct Node a,struct Node b){
    if(a.a/block==b.a/block)
        return a.b<b.b;
    return a.a/block<b.a/block;
}
int pb[N];
int dfs(int x){
mun[nn]=num[x];
po[x]=nn;
nn++;
vis[x]=1;
nnum[x]=1;
for(int i=0;i<v[x].size();i++){
    if(vis[v[x][i]]==0){
        nnum[x]+=dfs(v[x][i]);
    }
}
pb[x]=nn-1;
return nnum[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n+1;i++){
        scanf("%d",num+i);
    }
    int u,vv;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&vv);
        v[u].push_back(vv);
        v[vv].push_back(u);
    }
    dfs(1);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&node[i].a,&node[i].k);
        node[i].b=pb[node[i].a];
        node[i].a=po[node[i].a];
        node[i].id=i;
    }
    block=sqrt(n+0.5);
    sort(node+1,node+1+m,cmp);
    int l,r;l=1;r=0;
//    for(int i=1;i<nn;i++){
//        cout<<mun[i]<<" ";
//    }
//    cout<<endl;
    for(int i=1;i<=m;i++){
           // cout<<node[i].a<<" "<<node[i].b<<endl;
        while(l<node[i].a){
            del(l);l++;
        }while(l>node[i].a){
            l--;
            add(l);
        } while(r<node[i].b){
            r++;
            add(r);
        }while(r>node[i].b){
            del(r);
             r--;
        }
       en[node[i].id]=c[node[i].k];
    }
    for(int i=1;i<m+1;i++){
        printf("%d\n",en[i]);
    }
return 0;
}

没有强制转换成long long wa了2小时，心口子痛 T T ,以后一定不要犯了
求区间的组合数
I

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define N 100005
typedef long long ll;
struct Node{
int a,b,id;}node[N];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int num[N];
int cn[N];
ll ans=0;
ll en[N];
ll ff[N];
int n,m;
void add(int x){
   cn[num[x]]++;
   if(cn[num[x]]>1){
    ans+=cn[num[x]]-1;
   }
}
void del(int x){
    if(cn[num[x]]>1)
    {
        ans-=cn[num[x]]-1;
    }
    cn[num[x]]--;
}
int block;
bool cmp(struct Node a,struct Node b){

    if(a.a/block==b.a/block){
        return a.b<b.b;
    }
    return a.a/block<b.a/block;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n+1;i++){
        scanf("%d",num+i);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&node[i].a,&node[i].b);
        node[i].id=i;
    }
    block=sqrt(n+0.5);
    sort(node+1,node+1+m,cmp);
    int l,r;l=1;r=0;
    for(int i=1;i<=m;i++){
        while(l<node[i].a){
            del(l);l++;
        }while(l>node[i].a){
            l--;
            add(l);
        } while(r<node[i].b){
            r++;
            add(r);
        }while(r>node[i].b){
            del(r);
             r--;
        }
        en[node[i].id]=ans;
        ff[node[i].id]=ll(node[i].b-node[i].a+1)*(node[i].b-node[i].a)/2;
    }
    for(int i=1;i<m+1;i++){
        if(en[i]==0){
            printf("0/1\n");
        }else{


        ll temp=gcd(en[i],ff[i]);
        printf("%lld/%lld\n",en[i]/temp,ff[i]/temp);
        }
    }
return 0;
}