C++11(clang++ 3.9) 解法, 执行用时: 295ms, 内存消耗: 44144K, 提交时间: 2019-07-16 10:49:21

#include<bits/stdc++.h>
#define int long long
using namespace std;
int block,sum,Ans[5000005],p[5000005],n,m,Add[5000005],q;
int a[5000005],tlps[5000005],asqrt[5000005],dif[500005],d[10005];
int PKR[500005];
inline void work(int as,int bs,int x) {
    sort(asqrt + as,asqrt + bs + 1);
    sort(PKR + as,PKR + bs + 1);
    int st = 0;
    memset(d,0,sizeof(d));
    for (int i = as; i <= bs; i++) {
        st += a[i];
        if (!d[a[i]]) {
            d[a[i]]++;
            dif[x]++;
        }
    }
    Ans[x] = st;
}
signed main() {
    //freopen("dd5.in","r",stdin);
    //freopen("dd5.out","w",stdout);
    memset(Add,0,sizeof(Add));
    scanf("%lld%lld",&n,&q);
    block = (int)sqrt(n);
    sum = n / block; 
    if (n % block) sum++;
    for (int i = 1; i <= n; i++) {
        scanf("%lld",&a[i]);
        p[i] = (i - 1) / block + 1;
        asqrt[i] = a[i] - (int)sqrt(a[i]);
        PKR[i] = a[i];
        tlps[i] = asqrt[i];
    }
    for (int i = 1; i <= sum; i++)
        work((i - 1) * block + 1,min(i * block,n),i);
    for (int i = 1; i <= q; i++) {
        int x,y,op,k,st = 0;
        scanf("%lld%lld%lld",&x,&y,&k);
        for (int j = x; j <= min(p[x] * block,y); j++)
            st += a[j];
        if (p[x] != p[y])
            for (int j = (p[y] - 1) * block + 1; j <= y; j++)
                st += a[j];
        for (int j = p[x] + 1; j <= p[y] - 1; j++)
            st += Ans[j];
        int del = st - k;
        int v = 0;
        for (int j = x; j <= min(p[x] * block,y); j++)
            if (tlps[j] == del)
                v++;
        if (p[x] != p[y])
            for (int j = (p[y] - 1) * block + 1; j <= y; j++)
                if (tlps[j] == del)
                    v++;
        for (int j = p[x] + 1; j <= p[y] - 1; j++) {
            int low = lower_bound(asqrt + (j - 1) * block + 1,min(asqrt + n,asqrt + j * block + 1),del) - (asqrt + (j - 1) * block + 1);
            int upp = upper_bound(asqrt + (j - 1) * block + 1,min(asqrt + n,asqrt + j * block + 1),del) - (asqrt + (j - 1) * block + 1);            
            if (asqrt[low] == del && low - upp - 1 >= 0)
                v += low - upp - 1;else
            if (low >= upp)
              v += low - upp;
        }
        if (v <= 0)
            printf("Error\n");
        else {
            int diff = 0;
            memset(d,0,sizeof(d));
            for (int j = x; j <= min(p[x] * block,y); j++) {
                if (!d[a[j]] && tlps[j] == del) {
                    diff++;
                    d[a[j]]++;
                }
            }
            if (p[x] != p[y])
                for (int j = (p[y] - 1) * block + 1; j <= y; j++)
                    if (!d[a[j]] && tlps[j] == del) {
                        diff++;
                        d[a[j]]++;
                    }
            for (int j = p[x] + 1; j <= p[y] - 1; j++)
            {
                int upp = upper_bound(asqrt + (j - 1) * block + 1,min(asqrt + n,asqrt + j * block + 1),del) - (asqrt + (j - 1) * block + 1);            
                int low = lower_bound(asqrt + (j - 1) * block + 1,min(asqrt + n,asqrt + j * block + 1),del) - (asqrt + (j - 1) * block + 1);
                if (PKR[upp] != PKR[low] && upp != 0 && low != 0)
                  diff += 2;
            }
            if (diff <= 1)
                printf("pass\n");
            else
            if (diff > 1)
                printf("INF\n");
        }
    }
    return 0;
}