并不对劲的hdu4777-白红宇

并不对劲的hdu4777

阅读量：4608 次

发布时间：2019-06-09

本文共 3328 字，大约阅读时间需要 11 分钟。

　　Long long ago, there was an ancient rabbit kingdom in the forest. Every rabbit in this kingdom was not cute but totally pugnacious, so the kingdom was in chaos in season and out of season.

　　n rabbits were numbered form 1 to n. All rabbits' weight is an integer. For some unknown reason, two rabbits would fight each other if and only if their weight is NOT co-prime.

　　Now the king had arranged the n rabbits in a line ordered by their numbers. The king planned to send some rabbits into prison. He wanted to know that, if he sent all rabbits between the i-th one and the j-th one(including the i-th one and the j-th one) into prison, how many rabbits in the prison would not fight with others.

　　Please note that a rabbit would not fight with himself.

Input　　

The input consists of several test cases.

　The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries.

　The following line contains n integers, and the i-th integer W _i indicates the weight of the i-th rabbit.

　Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the L-th one to the R-th one into prison.

　(1 <= n, m, W _i <= 200000, 1 <= L <= R <= n)

　The input ends with n = 0 and m = 0.

Output　　

　For every query, output one line indicating the answer.Sample Input

3 22 1 41 21 36 43 6 1 2 5 31 34 64 42 60 0

Sample Output

Hint

　In the second case, the answer of the 4-th query is 2, because only 1 and 5 is co-prime with other numbers in the interval [2,6] .

——————————————————并不对劲的分界线——————————

听说很对劲的太刀流做出了本题，并不对劲的片手流为了反驳他，决定与他针锋相对。于是就也打算做这道题。

这题就是求区间内与区间内不包括自己所有数都互质的数有多少个。

先说个简单的小技巧：差分。想必大家都知道前缀和可以O(n)通过预处理，进行O(1)的查询。而差分刚好与前缀和相反，是O(1)修改，O(n)查询。实现方式也与前缀和相反。一开始有一个全是0的数列，每次对于[l,r]进行区间加k时，再

l处+k,r+1处-k，这样每个位置的前缀和表示这个位置加了多少数。查询次数只有一次时可以用这个，而且显然比线段树好写多了。

再看这一题，对于第x个w[x]，先通过分解质因数算出离它最近的两个与它不互质的数，分别记作pre[x],suf[x]。那么对于[l[i],r[i]]这一段区间，x会对解有贡献当且仅当pre[x]<l且r<suf[x]。

这时发现这有点像个二维偏序，那么一切都好办了。

好办个潜口龙啊！这个问题是找l>pre[x]且r<suf[x]且l<x<r的x有多少个！不过其实可以将询问按l排序，这样通过插入/删除，使得被统计的那些满足与l有关的条件。每次插入时，要将x到suf[x]-1区间+1，删除则是刚好反过来。那么答案就是r处对应的值了。会发现只有区间加和单点查，所以就可以用一开始说的树状数组差分了。

不得不说，细节还真麻烦…

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #define rep(i,x,y) for(register int i=(x);i<=(y);i++)#define dwn(i,x,y) for(register int i=(x);i>=(y);i--)#define maxn 200002using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}inline void write(int x){ int f=0;char ch[20]; if(!x){puts("0");return;} if(x<0){putchar('-');x=-x;} while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n');}typedef struct que{int l,r,ord,ans;} Q;vector
                
                 v[maxn];Q q[maxn];bool isp[maxn];int n,m,w[maxn],fir[maxn],l[maxn],r[maxn],ord[maxn],hd,tr[maxn];inline int lt(int x){return x&-x;}inline int ask(int i){int ans=0;for(;i;i-=lt(i))ans+=tr[i];return ans;}inline void add(int i,int k){for(;i<=n;i+=lt(i))tr[i]+=k;}bool cmpl(Q x,Q y){return x.l==y.l?x.r

转载于:https://www.cnblogs.com/xzyf/p/8623049.html

你可能感兴趣的文章