D题题解：

方法： $\theta(nlogn)$ 数学解法

思路：

查询保证了有且仅有两个数只出现1次，其他都是2次

设这两个数分别为 $x$ 、 $y$ ，不妨让 $x<y$

我们可以想办法，搞一种前缀和，两个一样的数会消掉，正常人会想到异或，求区间异或和我们就能得到 $x \oplus y$ ，以为需要求其中一个值，比较麻烦，我们不考虑这个做法。~~（我不会求其中一个值）~~

换一种思路，如果我把第偶数次出现的数改为它的负数，那么前缀和求值，得到 $\pm x \pm y$ 的值 $wa$ ；同理，如果对原数组的平方数组（每个数为原数的平方）同样做，能够得到 $\pm x^2 \pm y^2$ 的的值 $wb$ 。为了方便取个绝对值。

因为 $x$ 与 $x^2$ 同号， $y$ 与 $y^2$ 同号，故 $wa$ 与 $wb$ 只有两种情况：

$wa=y-x,wb=y^2-x^2$ ，这个好求， $x y=\frac{wb}{wa}$ ，然后直接得到 $x,y$ 。

被hack了：

$wa=x y,wb=x^2 y^2$ ，因为 $x\neq y$ ，因此 $wb\pmod{wa}\neq 0$ ，因此可以和上一个情况区分开来。考虑解方程， $x=wa-y$ ，带入 $wb$ 中得到： $(y-\frac{wa}{2})^2=\frac{wb}{2}-\frac{wa^2}{4}$ ， $x$ 的方程也是如此（把 $y$ 换成 $x$ ）。因此 $x,y$ 为方程的两个解，直接求即可。

修正后：

$wa=x y,wb=x^2 y^2$ ，考虑解方程， $x=wa-y$ ，带入 $wb$ 中得到： $(y-\frac{wa}{2})^2=\frac{wb}{2}-\frac{wa^2}{4}$ ， $x$ 的方程也是如此（把 $y$ 换成 $x$ ）。因此 $x,y$ 为方程的两个解。

如何区分是第一种情况还是第二种情况？

我们先假装是第一种情况，然后查找这个 $x,y$ 是不是我们要的两个值，如果不满足在区间中仅有一个，那么就再按第二种情况来算。

使用vector记录每个值的下标，每次检验时，二分查找在 l,r 范围的下标数量。

~~因为没有奇怪的测试点，时间依旧优秀~~

完整代码：

#include<bits/stdc++.h>
#define ll long long
#define MN 0.000001
#define MXN 1000002
using namespace std;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}

ll T=1,n,q,a[MXN],b[MXN],ans;//a为原数组前缀和,b为平方数组前缀和
vector<ll>nt[MXN];
bool v[MXN];
ll find(ll x,ll l,ll r){//查找x在区间[l,r]中的个数
    if(x<=0||x>=MXN) return 0;
    return upper_bound(nt[x].begin(),nt[x].end(),r)-lower_bound(nt[x].begin(),nt[x].end(),l);
}
void solve(){
    rd(n),rd(q);
    for(ll i=1;i<=n;i++){
        rd(a[i]);
        nt[a[i]].push_back(i);//用于查找某值的个数
        b[i]=a[i]*a[i];
        v[a[i]]^=1;
        if(!v[a[i]]) a[i]=-a[i],b[i]=-b[i];//如果是第偶数次出现，将其变为负数
        a[i]+=a[i-1],b[i]+=b[i-1];
    }
    while(q--){
        ll l,r;
        rd(l),rd(r);
        ll wa=abs(a[r]-a[l-1]),wb=abs(b[r]-b[l-1]);
        ll del=wa,add=wb/wa;
        ll x=(del+add)/2,y=abs(del-add)/2;
        if(find(x,l,r)!=1||find(y,l,r)!=1){//两者之和的情况，如果x,y在区间中不同时为1
            double c=sqrt(wb/2-wa*wa/4.0);
            x=-c+wa/2.0+0.1,y=c+wa/2.0+0.1;//解方程，解一定是整数，0.1是为了抵消浮点数误差，以防万一
            pt(x),putchar(' '),pt(y),puts("");
        }else pt(min(x,y)),putchar(' '),pt(max(x,y)),puts("");//两者之差的情况
    }
}int main(){while(T--) solve();}

被hack代码：

//这份考虑出了问题
#include<bits/stdc++.h>
#define ll long long
#define MXN 1000002
using namespace std;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}

ll T=1,n,q,a[MXN],b[MXN],ans;//a为原数组前缀和,b为平方数组前缀和
bool v[MXN];
void solve(){
    rd(n),rd(q);
    for(ll i=1;i<=n;i++){
        rd(a[i]);
        b[i]=a[i]*a[i];
        v[a[i]]^=1;
        if(!v[a[i]]) a[i]=-a[i],b[i]=-b[i];//如果是第偶数次出现，将其变为负数
        a[i]+=a[i-1],b[i]+=b[i-1];
    }
    while(q--){
        ll l,r;
        rd(l),rd(r);
        ll wa=abs(a[r]-a[l-1]),wb=abs(b[r]-b[l-1]);
        if(wb%wa){//两者之和的情况
            double c=sqrt(wb/2-wa*wa/4.0);
            ll x=-c+wa/2.0+0.1,y=c+wa/2.0+0.1;//解方程，解一定是整数，0.1是为了抵消浮点数误差，以防万一
            pt(x),putchar(' '),pt(y),puts("");
        }else{//两者之差的情况
            ll del=wa,add=wb/wa;
            ll x=(del+add)/2,y=abs(del-add)/2;
            pt(min(x,y)),putchar(' '),pt(max(x,y)),puts("");
        }
    }
}int main(){while(T--) solve();}

题解 | #找更多的数字#

D题题解：

思路：

完整代码：