您当前的位置: 首页 > 

暂无认证

  • 12浏览

    0关注

    93978博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

P1494 [国家集训队] 小 Z 的袜子

发布时间:2022-09-23 16:09:37 ,浏览量:12

在这里插入图片描述 问题:解决 q q q次询问,每次询问 [ L , R ] [L,R] [L,R]中有多少对 ( i , j ) , 满足 a i = = a j (i,j),满足a_i==a_j (i,j),满足ai==aj 先想点超时但是可以解决的方法: 对于每次询问,枚举 L < = i < = R L<=i<=R L<=i<=R中的元素,令 n u m [ i ] num[i] num[i]为 i i i元素出现的次数,显然这样的对数是 n u m [ i ] ∗ ( n u m [ i ] − 1 ) / 2 num[i]*(num[i]-1)/2 num[i]∗(num[i]−1)/2 注意下题目似乎是静态的,并不是动态的。也许可以利用这点. 然而并没有想出来,据说是一种叫莫队的算法。 学习完莫队,发现这是莫队的板子题,真是富有启发性。 利用查询区间之间的信息,进行信息合并,很美妙的一个算法.

/*
Tonight I wanna drown in an ocean of you
*/ #include using namespace std; const int INF = 1e9+7; const int maxn = 1e6+5; typedef long long ll; typedef pair<int,int> pii; #define all(a) (a).begin(), (a).end() #define pb(a) push_back(a) vector<int> G[maxn]; int mx; struct Node{ int l,r,id; bool operator < (const Node &rhs)const{ if(l/mx!=rhs.l/mx) return l<rhs.l; if((l/mx)&1) return r < rhs.r; return r>rhs.r; } };//询问序列 Node q[maxn]; ll sum = 0;int cnt[maxn];int a[maxn]; void add(int i){ sum += cnt[i]; cnt[i]++; } void del(int i){ cnt[i]--; sum -= cnt[i]; } ll gcd(ll a,ll b){ if(!b) return a; return gcd(b,a%b); } ll ans1[maxn],ans2[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; mx = n / sqrt(n*2/3); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<m;i++) cin>>q[i].l>>q[i].r,q[i].id = i; sort(q,q+m); for(int i=0,l=1,r=0;i<m;i++){ if(q[i].l==q[i].r){ ans1[q[i].id] = 0,ans2[q[i].id] = 1; continue; } while(l>q[i].l) add(a[--l]); while(r<q[i].r) add(a[++r]); while(l<q[i].l) del(a[l++]); while(r>q[i].r) del(a[r--]); ans1[q[i].id] = sum; //分子 ans2[q[i].id] = 1LL*(r-l+1)*(r-l)/2; //分母 } for(int i=0;i<m;i++){ if(ans1[i]!=0){ ll g = gcd(ans1[i],ans2[i]); ans1[i]/=g,ans2[i]/=g; } else ans2[i] = 1; cout<<ans1[i]<<"/"<<ans2[i]<<"\n"; } } 
关注
打赏
1655516835
查看更多评论
立即登录/注册

微信扫码登录

0.0495s